All posts by dotte

七天学会NodeJS

NodeJS基础

什么是NodeJS

JS是脚本语言,脚本语言都需要一个解析器才能运行。对于写在HTML页面里的JS,浏览器充当了解析器的角色。而对于需要独立运行的JS,NodeJS就是一个解析器。

每一种解析器都是一个运行环境,不但允许JS定义各种数据结构,进行各种计算,还允许JS使用运行环境提供的内置对象和方法做一些事情。例如运行在浏览器中的JS的用途是操作DOM,浏览器就提供了document之类的内置对象。而运行在NodeJS中的JS的用途是操作磁盘文件或搭建HTTP服务器,NodeJS就相应提供了fshttp等内置对象。

有啥用处

尽管存在一听说可以直接运行JS文件就觉得很酷的同学,但大多数同学在接触新东西时首先关心的是有啥用处,以及能带来啥价值。

NodeJS的作者说,他创造NodeJS的目的是为了实现高性能Web服务器,他首先看重的是事件机制和异步IO模型的优越性,而不是JS。但是他需要选择一种编程语言实现他的想法,这种编程语言不能自带IO功能,并且需要能良好支持事件机制。JS没有自带IO功能,天生就用于处理浏览器中的DOM事件,并且拥有一大群程序员,因此就成为了天然的选择。

如他所愿,NodeJS在服务端活跃起来,出现了大批基于NodeJS的Web服务。而另一方面,NodeJS让前端众如获神器,终于可以让自己的能力覆盖范围跳出浏览器窗口,更大批的前端工具如雨后春笋。

因此,对于前端而言,虽然不是人人都要拿NodeJS写一个服务器程序,但简单可至使用命令交互模式调试JS代码片段,复杂可至编写工具提升工作效率。

NodeJS生态圈正欣欣向荣。

如何安装

安装程序

NodeJS提供了一些安装程序,都可以在nodejs.org这里下载并安装。

Windows系统下,选择和系统版本匹配的.msi后缀的安装文件。Mac OS X系统下,选择.pkg后缀的安装文件。

编译安装

Linux系统下没有现成的安装程序可用,虽然一些发行版可以使用apt-get之类的方式安装,但不一定能安装到最新版。因此Linux系统下一般使用以下方式编译方式安装NodeJS。

  1. 确保系统下g++版本在4.6以上,python版本在2.6以上。
  2. nodejs.org下载tar.gz后缀的NodeJS最新版源代码包并解压到某个位置。
  3. 进入解压到的目录,使用以下命令编译和安装。
     $ ./configure $ make $ sudo make install

如何运行

打开终端,键入node进入命令交互模式,可以输入一条代码语句后立即执行并显示结果,例如:

$ node > console.log('Hello World!'); Hello World!

如果要运行一大段代码的话,可以先写一个JS文件再运行。例如有以下hello.js

function hello() { console.log('Hello World!'); } hello();

写好后在终端下键入node hello.js运行,结果如下:

$ node hello.js Hello World!

权限问题

在Linux系统下,使用NodeJS监听80或443端口提供HTTP(S)服务时需要root权限,有两种方式可以做到。

一种方式是使用sudo命令运行NodeJS。例如通过以下命令运行的server.js中有权限使用80和443端口。一般推荐这种方式,可以保证仅为有需要的JS脚本提供root权限。

$ sudo node server.js

另一种方式是使用chmod +s命令让NodeJS总是以root权限运行,具体做法如下。因为这种方式让任何JS脚本都有了root权限,不太安全,因此在需要很考虑安全的系统下不推荐使用。

$ sudo chown root /usr/local/bin/node $ sudo chmod +s /usr/local/bin/node

模块

编写稍大一点的程序时一般都会将代码模块化。在NodeJS中,一般将代码合理拆分到不同的JS文件中,每一个文件就是一个模块,而文件路径就是模块名。

在编写每个模块时,都有requireexportsmodule三个预先定义好的变量可供使用。

require

require函数用于在当前模块中加载和使用别的模块,传入一个模块名,返回一个模块导出对象。模块名可使用相对路径(以./开头),或者是绝对路径(以/C:之类的盘符开头)。另外,模块名中的.js扩展名可以省略。以下是一个例子。

var foo1 = require('./foo'); var foo2 = require('./foo.js'); var foo3 = require('/home/user/foo'); var foo4 = require('/home/user/foo.js'); // foo1至foo4中保存的是同一个模块的导出对象。

另外,可以使用以下方式加载和使用一个JSON文件。

var data = require('./data.json');

exports

exports对象是当前模块的导出对象,用于导出模块公有方法和属性。别的模块通过require函数使用当前模块时得到的就是当前模块的exports对象。以下例子中导出了一个公有方法。

exports.hello = function () { console.log('Hello World!'); };

module

通过module对象可以访问到当前模块的一些相关信息,但最多的用途是替换当前模块的导出对象。例如模块导出对象默认是一个普通对象,如果想改成一个函数的话,可以使用以下方式。

module.exports = function () { console.log('Hello World!'); };

以上代码中,模块默认导出对象被替换为一个函数。

模块初始化

一个模块中的JS代码仅在模块第一次被使用时执行一次,并在执行过程中初始化模块的导出对象。之后,缓存起来的导出对象被重复利用。

主模块

通过命令行参数传递给NodeJS以启动程序的模块被称为主模块。主模块负责调度组成整个程序的其它模块完成工作。例如通过以下命令启动程序时,main.js就是主模块。

$ node main.js

完整示例

例如有以下目录。

- /home/user/hello/ - util/ counter.js main.js

其中counter.js内容如下:

var i = 0; function count() { return ++i; } exports.count = count;

该模块内部定义了一个私有变量i,并在exports对象导出了一个公有方法count

主模块main.js内容如下:

var counter1 = require('./util/counter'); var counter2 = require('./util/counter'); console.log(counter1.count()); console.log(counter2.count()); console.log(counter2.count());

运行该程序的结果如下:

$ node main.js 1 2 3

可以看到,counter.js并没有因为被require了两次而初始化两次。

二进制模块

虽然一般我们使用JS编写模块,但NodeJS也支持使用C/C++编写二进制模块。编译好的二进制模块除了文件扩展名是.node外,和JS模块的使用方式相同。虽然二进制模块能使用操作系统提供的所有功能,拥有无限的潜能,但对于前端同学而言编写过于困难,并且难以跨平台使用,因此不在本教程的覆盖范围内。

小结

本章介绍了有关NodeJS的基本概念和使用方法,总结起来有以下知识点:

  • NodeJS是一个JS脚本解析器,任何操作系统下安装NodeJS本质上做的事情都是把NodeJS执行程序复制到一个目录,然后保证这个目录在系统PATH环境变量下,以便终端下可以使用node命令。
  • 终端下直接输入node命令可进入命令交互模式,很适合用来测试一些JS代码片段,比如正则表达式。
  • NodeJS使用CMD模块系统,主模块作为程序入口点,所有模块在执行过程中只初始化一次。
  • 除非JS模块不能满足需求,否则不要轻易使用二进制模块,否则你的用户会叫苦连天。

代码的组织和部署

有经验的C程序员在编写一个新程序时首先从make文件写起。同样的,使用NodeJS编写程序前,为了有个良好的开端,首先需要准备好代码的目录结构和部署方式,就如同修房子要先搭脚手架。本章将介绍与之相关的各种知识。

模块路径解析规则

我们已经知道,require函数支持斜杠(/)或盘符(C:)开头的绝对路径,也支持./开头的相对路径。但这两种路径在模块之间建立了强耦合关系,一旦某个模块文件的存放位置需要变更,使用该模块的其它模块的代码也需要跟着调整,变得牵一发动全身。因此,require函数支持第三种形式的路径,写法类似于foo/bar,并依次按照以下规则解析路径,直到找到模块位置。

  1. 内置模块如果传递给require函数的是NodeJS内置模块名称,不做路径解析,直接返回内部模块的导出对象,例如require('fs')
  2. node_modules目录NodeJS定义了一个特殊的node_modules目录用于存放模块。例如某个模块的绝对路径是/home/user/hello.js,在该模块中使用require('foo/bar')方式加载模块时,则NodeJS依次尝试使用以下路径。
     /home/user/node_modules/foo/bar /home/node_modules/foo/bar /node_modules/foo/bar
  3. NODE_PATH环境变量与PATH环境变量类似,NodeJS允许通过NODE_PATH环境变量来指定额外的模块搜索路径。NODE_PATH环境变量中包含一到多个目录路径,路径之间在Linux下使用:分隔,在Windows下使用;分隔。例如定义了以下NODE_PATH环境变量:
     NODE_PATH=/home/user/lib:/home/lib

    当使用require('foo/bar')的方式加载模块时,则NodeJS依次尝试以下路径。

     /home/user/lib/foo/bar /home/lib/foo/bar

包(package)

我们已经知道了JS模块的基本单位是单个JS文件,但复杂些的模块往往由多个子模块组成。为了便于管理和使用,我们可以把由多个子模块组成的大模块称做,并把所有子模块放在同一个目录里。

在组成一个包的所有子模块中,需要有一个入口模块,入口模块的导出对象被作为包的导出对象。例如有以下目录结构。

- /home/user/lib/ - cat/ head.js body.js main.js

其中cat目录定义了一个包,其中包含了3个子模块。main.js作为入口模块,其内容如下:

var head = require('./head'); var body = require('./body'); exports.create = function (name) { return { name: name, head: head.create(), body: body.create() }; };

在其它模块里使用包的时候,需要加载包的入口模块。接着上例,使用require('/home/user/lib/cat/main')能达到目的,但是入口模块名称出现在路径里看上去不是个好主意。因此我们需要做点额外的工作,让包使用起来更像是单个模块。

index.js

当模块的文件名是index.js,加载模块时可以使用模块所在目录的路径代替模块文件路径,因此接着上例,以下两条语句等价。

var cat = require('/home/user/lib/cat'); var cat = require('/home/user/lib/cat/index');

这样处理后,就只需要把包目录路径传递给require函数,感觉上整个目录被当作单个模块使用,更有整体感。

package.json

如果想自定义入口模块的文件名和存放位置,就需要在包目录下包含一个package.json文件,并在其中指定入口模块的路径。上例中的cat模块可以重构如下。

- /home/user/lib/ - cat/ + doc/ - lib/ head.js body.js main.js + tests/ package.json

其中package.json内容如下。

{ "name": "cat", "main": "./lib/main.js" }

如此一来,就同样可以使用require('/home/user/lib/cat')的方式加载模块。NodeJS会根据包目录下的package.json找到入口模块所在位置。

命令行程序

使用NodeJS编写的东西,要么是一个包,要么是一个命令行程序,而前者最终也会用于开发后者。因此我们在部署代码时需要一些技巧,让用户觉得自己是在使用一个命令行程序。

例如我们用NodeJS写了个程序,可以把命令行参数原样打印出来。该程序很简单,在主模块内实现了所有功能。并且写好后,我们把该程序部署在/home/user/bin/node-echo.js这个位置。为了在任何目录下都能运行该程序,我们需要使用以下终端命令。

$ node /home/user/bin/node-echo.js Hello World Hello World

这种使用方式看起来不怎么像是一个命令行程序,下边的才是我们期望的方式。

$ node-echo Hello World

Linux

在Linux系统下,我们可以把JS文件当作shell脚本来运行,从而达到上述目的,具体步骤如下:

  1. 在shell脚本中,可以通过#!注释来指定当前脚本使用的解析器。所以我们首先在node-echo.js文件顶部增加以下一行注释,表明当前脚本使用NodeJS解析。
     #! /usr/bin/env node

    NodeJS会忽略掉位于JS模块首行的#!注释,不必担心这行注释是非法语句。

  2. 然后,我们使用以下命令赋予node-echo.js文件执行权限。
     $ chmod +x /home/user/bin/node-echo.js
  3. 最后,我们在PATH环境变量中指定的某个目录下,例如在/usr/local/bin下边创建一个软链文件,文件名与我们希望使用的终端命令同名,命令如下:
     $ sudo ln -s /home/user/bin/node-echo.js /usr/local/bin/node-echo

这样处理后,我们就可以在任何目录下使用node-echo命令了。

Windows

在Windows系统下的做法完全不同,我们得靠.cmd文件来解决问题。假设node-echo.js存放在C:\Users\user\bin目录,并且该目录已经添加到PATH环境变量里了。接下来需要在该目录下新建一个名为node-echo.cmd的文件,文件内容如下:

@node "C:\User\user\bin\node-echo.js" %*

这样处理后,我们就可以在任何目录下使用node-echo命令了。

工程目录

了解了以上知识后,现在我们可以来完整地规划一个工程目录了。以编写一个命令行程序为例,一般我们会同时提供命令行模式和API模式两种使用方式,并且我们会借助三方包来编写代码。除了代码外,一个完整的程序也应该有自己的文档和测试用例。因此,一个标准的工程目录都看起来像下边这样。

- /home/user/workspace/node-echo/ # 工程目录 - bin/ # 存放命令行相关代码 node-echo + doc/ # 存放文档 - lib/ # 存放API相关代码 echo.js - node_modules/ # 存放三方包 + argv/ + tests/ # 存放测试用例 package.json # 元数据文件 README.md # 说明文件

其中部分文件内容如下:

/* bin/node-echo */ var argv = require('argv'), echo = require('../lib/echo'); console.log(echo(argv.join(' '))); /* lib/echo.js */ module.exports = function (message) { return message; }; /* package.json */ { "name": "node-echo", "main": "./lib/echo.js" }

以上例子中分类存放了不同类型的文件,并通过node_moudles目录直接使用三方包名加载模块。此外,定义了package.json之后,node-echo目录也可被当作一个包来使用。

NPM

NPM是随同NodeJS一起安装的包管理工具,能解决NodeJS代码部署上的很多问题,常见的使用场景有以下几种:

  • 允许用户从NPM服务器下载别人编写的三方包到本地使用。
  • 允许用户从NPM服务器下载并安装别人编写的命令行程序到本地使用。
  • 允许用户将自己编写的包或命令行程序上传到NPM服务器供别人使用。

可以看到,NPM建立了一个NodeJS生态圈,NodeJS开发者和用户可以在里边互通有无。以下分别介绍这三种场景下怎样使用NPM。

下载三方包

需要使用三方包时,首先得知道有哪些包可用。虽然npmjs.org提供了个搜索框可以根据包名来搜索,但如果连想使用的三方包的名字都不确定的话,就请百度一下吧。知道了包名后,比如上边例子中的argv,就可以在工程目录下打开终端,使用以下命令来下载三方包。

$ npm install argv ... argv@0.0.2 node_modules\argv

下载好之后,argv包就放在了工程目录下的node_modules目录中,因此在代码中只需要通过require('argv')的方式就好,无需指定三方包路径。

以上命令默认下载最新版三方包,如果想要下载指定版本的话,可以在包名后边加上@<version>,例如通过以下命令可下载0.0.1版的argv

$ npm install argv@0.0.1 ... argv@0.0.1 node_modules\argv

如果使用到的三方包比较多,在终端下一个包一条命令地安装未免太人肉了。因此NPM对package.json的字段做了扩展,允许在其中申明三方包依赖。因此,上边例子中的package.json可以改写如下:

{ "name": "node-echo", "main": "./lib/echo.js", "dependencies": { "argv": "0.0.2" } }

这样处理后,在工程目录下就可以使用npm install命令批量安装三方包了。更重要的是,当以后node-echo也上传到了NPM服务器,别人下载这个包时,NPM会根据包中申明的三方包依赖自动下载进一步依赖的三方包。例如,使用npm install node-echo命令时,NPM会自动创建以下目录结构。

- project/ - node_modules/ - node-echo/ - node_modules/ + argv/ ... ...

如此一来,用户只需关心自己直接使用的三方包,不需要自己去解决所有包的依赖关系。

安装命令行程序

从NPM服务上下载安装一个命令行程序的方法与三方包类似。例如上例中的node-echo提供了命令行使用方式,只要node-echo自己配置好了相关的package.json字段,对于用户而言,只需要使用以下命令安装程序。

$ npm install node-echo -g

参数中的-g表示全局安装,因此node-echo会默认安装到以下位置,并且NPM会自动创建好Linux系统下需要的软链文件或Windows系统下需要的.cmd文件。

- /usr/local/ # Linux系统下 - lib/node_modules/ + node-echo/ ... - bin/ node-echo ... ... - %APPDATA%\npm\ # Windows系统下 - node_modules\ + node-echo\ ... node-echo.cmd ...

发布代码

第一次使用NPM发布代码前需要注册一个账号。终端下运行npm adduser,之后按照提示做即可。账号搞定后,接着我们需要编辑package.json文件,加入NPM必需的字段。接着上边node-echo的例子,package.json里必要的字段如下。

{ "name": "node-echo", # 包名,在NPM服务器上须要保持唯一 "version": "1.0.0", # 当前版本号 "dependencies": { # 三方包依赖,需要指定包名和版本号 "argv": "0.0.2" }, "main": "./lib/echo.js", # 入口模块位置 "bin" : { "node-echo": "./bin/node-echo" # 命令行程序名和主模块位置 } }

之后,我们就可以在package.json所在目录下运行npm publish发布代码了。

版本号

使用NPM下载和发布代码时都会接触到版本号。NPM使用语义版本号来管理代码,这里简单介绍一下。

语义版本号分为X.Y.Z三位,分别代表主版本号、次版本号和补丁版本号。当代码变更时,版本号按以下原则更新。

+ 如果只是修复bug,需要更新Z位。 + 如果是新增了功能,但是向下兼容,需要更新Y位。 + 如果有大变动,向下不兼容,需要更新X位。

版本号有了这个保证后,在申明三方包依赖时,除了可依赖于一个固定版本号外,还可依赖于某个范围的版本号。例如"argv": "0.0.x"表示依赖于0.0.x系列的最新版argv。NPM支持的所有版本号范围指定方式可以查看官方文档

灵机一点

除了本章介绍的部分外,NPM还提供了很多功能,package.json里也有很多其它有用的字段。除了可以在npmjs.org/doc/查看官方文档外,这里再介绍一些NPM常用命令。

  • NPM提供了很多命令,例如installpublish,使用npm help可查看所有命令。
  • 使用npm help <command>可查看某条命令的详细帮助,例如npm help install
  • package.json所在目录下使用npm install . -g可先在本地安装当前命令行程序,可用于发布前的本地测试。
  • 使用npm update <package>可以把当前目录下node_modules子目录里边的对应模块更新至最新版本。
  • 使用npm update <package> -g可以把全局安装的对应命令行程序更新至最新版。
  • 使用npm cache clear可以清空NPM本地缓存,用于对付使用相同版本号发布新版本代码的人。
  • 使用npm unpublish <package>@<version>可以撤销发布自己发布过的某个版本代码。

小结

本章介绍了使用NodeJS编写代码前需要做的准备工作,总结起来有以下几点:

  • 编写代码前先规划好目录结构,才能做到有条不紊。
  • 稍大些的程序可以将代码拆分为多个模块管理,更大些的程序可以使用包来组织模块。
  • 合理使用node_modulesNODE_PATH来解耦包的使用方式和物理路径。
  • 使用NPM加入NodeJS生态圈互通有无。
  • 想到了心仪的包名时请提前在NPM上抢注。

文件操作

让前端觉得如获神器的不是NodeJS能做网络编程,而是NodeJS能够操作文件。小至文件查找,大至代码编译,几乎没有一个前端工具不操作文件。换个角度讲,几乎也只需要一些数据处理逻辑,再加上一些文件操作,就能够编写出大多数前端工具。本章将介绍与之相关的NodeJS内置模块。

开门红

NodeJS提供了基本的文件操作API,但是像文件拷贝这种高级功能就没有提供,因此我们先拿文件拷贝程序练手。与copy命令类似,我们的程序需要能接受源文件路径与目标文件路径两个参数。

小文件拷贝

我们使用NodeJS内置的fs模块简单实现这个程序如下。

var fs = require('fs'); function copy(src, dst) { fs.writeFileSync(dst, fs.readFileSync(src)); } function main(argv) { copy(argv[0], argv[1]); } main(process.argv.slice(2));

以上程序使用fs.readFileSync从源路径读取文件内容,并使用fs.writeFileSync将文件内容写入目标路径。

豆知识: process是一个全局变量,可通过process.argv获得命令行参数。由于argv[0]固定等于NodeJS执行程序的绝对路径,argv[1]固定等于主模块的绝对路径,因此第一个命令行参数从argv[2]这个位置开始。

大文件拷贝

上边的程序拷贝一些小文件没啥问题,但这种一次性把所有文件内容都读取到内存中后再一次性写入磁盘的方式不适合拷贝大文件,内存会爆仓。对于大文件,我们只能读一点写一点,直到完成拷贝。因此上边的程序需要改造如下。

var fs = require('fs'); function copy(src, dst) { fs.createReadStream(src).pipe(fs.createWriteStream(dst)); } function main(argv) { copy(argv[0], argv[1]); } main(process.argv.slice(2));

以上程序使用fs.createReadStream创建了一个源文件的只读数据流,并使用fs.createWriteStream创建了一个目标文件的只写数据流,并且用pipe方法把两个数据流连接了起来。连接起来后发生的事情,说得抽象点的话,水顺着水管从一个桶流到了另一个桶。

API走马观花

我们先大致看看NodeJS提供了哪些和文件操作有关的API。这里并不逐一介绍每个API的使用方法,官方文档已经做得很好了。

Buffer(数据块)

官方文档: http://nodejs.org/api/buffer.html

JS语言自身只有字符串数据类型,没有二进制数据类型,因此NodeJS提供了一个与String对等的全局构造函数Buffer来提供对二进制数据的操作。除了可以读取文件得到Buffer的实例外,还能够直接构造,例如:

var bin = new Buffer([ 0x68, 0x65, 0x6c, 0x6c, 0x6f ]);

Buffer与字符串类似,除了可以用.length属性得到字节长度外,还可以用[index]方式读取指定位置的字节,例如:

bin[0]; // => 0x68;

Buffer与字符串能够互相转化,例如可以使用指定编码将二进制数据转化为字符串:

var str = bin.toString('utf-8'); // => "hello"

或者反过来,将字符串转换为指定编码下的二进制数据:

var bin = new Buffer('hello', 'utf-8'); // => <Buffer 68 65 6c 6c 6f>

Buffer与字符串有一个重要区别。字符串是只读的,并且对字符串的任何修改得到的都是一个新字符串,原字符串保持不变。至于Buffer,更像是可以做指针操作的C语言数组。例如,可以用[index]方式直接修改某个位置的字节。

bin[0] = 0x48;

.slice方法也不是返回一个新的Buffer,而更像是返回了指向原Buffer中间的某个位置的指针,如下所示。

[ 0x68, 0x65, 0x6c, 0x6c, 0x6f ] ^ ^ | | bin bin.slice(2)

因此对.slice方法返回的Buffer的修改会作用于原Buffer,例如:

var bin = new Buffer([ 0x68, 0x65, 0x6c, 0x6c, 0x6f ]); var sub = bin.slice(2); sub[0] = 0x65; console.log(bin); // => <Buffer 68 65 65 6c 6f>

也因此,如果想要拷贝一份Buffer,得首先创建一个新的Buffer,并通过.copy方法把原Buffer中的数据复制过去。这个类似于申请一块新的内存,并把已有内存中的数据复制过去。以下是一个例子。

var bin = new Buffer([ 0x68, 0x65, 0x6c, 0x6c, 0x6f ]); var dup = new Buffer(bin.length); bin.copy(dup); dup[0] = 0x48; console.log(bin); // => <Buffer 68 65 6c 6c 6f> console.log(dup); // => <Buffer 48 65 65 6c 6f>

总之,Buffer将JS的数据处理能力从字符串扩展到了任意二进制数据。

Stream(数据流)

官方文档: http://nodejs.org/api/stream.html

当内存中无法一次装下需要处理的数据时,或者一边读取一边处理更加高效时,我们就需要用到数据流。NodeJS中通过各种Stream来提供对数据流的操作。

以上边的大文件拷贝程序为例,我们可以为数据来源创建一个只读数据流,示例如下:

var rs = fs.createReadStream(pathname); rs.on('data', function (chunk) { doSomething(chunk); }); rs.on('end', function () { cleanUp(); });

豆知识: Stream基于事件机制工作,所有Stream的实例都继承于NodeJS提供的EventEmitter

上边的代码中data事件会源源不断地被触发,不管doSomething函数是否处理得过来。代码可以继续做如下改造,以解决这个问题。

var rs = fs.createReadStream(src); rs.on('data', function (chunk) { rs.pause(); doSomething(chunk, function () { rs.resume(); }); }); rs.on('end', function () { cleanUp(); });

以上代码给doSomething函数加上了回调,因此我们可以在处理数据前暂停数据读取,并在处理数据后继续读取数据。

此外,我们也可以为数据目标创建一个只写数据流,示例如下:

var rs = fs.createReadStream(src); var ws = fs.createWriteStream(dst); rs.on('data', function (chunk) { ws.write(chunk); }); rs.on('end', function () { ws.end(); });

我们把doSomething换成了往只写数据流里写入数据后,以上代码看起来就像是一个文件拷贝程序了。但是以上代码存在上边提到的问题,如果写入速度跟不上读取速度的话,只写数据流内部的缓存会爆仓。我们可以根据.write方法的返回值来判断传入的数据是写入目标了,还是临时放在了缓存了,并根据drain事件来判断什么时候只写数据流已经将缓存中的数据写入目标,可以传入下一个待写数据了。因此代码可以改造如下:

var rs = fs.createReadStream(src); var ws = fs.createWriteStream(dst); rs.on('data', function (chunk) { if (ws.write(chunk) === false) { rs.pause(); } }); rs.on('end', function () { ws.end(); }); ws.on('drain', function () { rs.resume(); });

以上代码实现了数据从只读数据流到只写数据流的搬运,并包括了防爆仓控制。因为这种使用场景很多,例如上边的大文件拷贝程序,NodeJS直接提供了.pipe方法来做这件事情,其内部实现方式与上边的代码类似。

File System(文件系统)

官方文档: http://nodejs.org/api/fs.html

NodeJS通过fs内置模块提供对文件的操作。fs模块提供的API基本上可以分为以下三类:

  • 文件属性读写。其中常用的有fs.statfs.chmodfs.chown等等。
  • 文件内容读写。其中常用的有fs.readFilefs.readdirfs.writeFilefs.mkdir等等。
  • 底层文件操作。其中常用的有fs.openfs.readfs.writefs.close等等。

NodeJS最精华的异步IO模型在fs模块里有着充分的体现,例如上边提到的这些API都通过回调函数传递结果。以fs.readFile为例:

fs.readFile(pathname, function (err, data) { if (err) { // Deal with error. } else { // Deal with data. } });

如上边代码所示,基本上所有fs模块API的回调参数都有两个。第一个参数在有错误发生时等于异常对象,第二个参数始终用于返回API方法执行结果。

此外,fs模块的所有异步API都有对应的同步版本,用于无法使用异步操作时,或者同步操作更方便时的情况。同步API除了方法名的末尾多了一个Sync之外,异常对象与执行结果的传递方式也有相应变化。同样以fs.readFileSync为例:

try { var data = fs.readFileSync(pathname); // Deal with data. } catch (err) { // Deal with error. }

fs模块提供的API很多,这里不一一介绍,需要时请自行查阅官方文档。

Path(路径)

官方文档: http://nodejs.org/api/path.html

操作文件时难免不与文件路径打交道。NodeJS提供了path内置模块来简化路径相关操作,并提升代码可读性。以下分别介绍几个常用的API。

  • path.normalize将传入的路径转换为标准路径,具体讲的话,除了解析路径中的...外,还能去掉多余的斜杠。如果有程序需要使用路径作为某些数据的索引,但又允许用户随意输入路径时,就需要使用该方法保证路径的唯一性。以下是一个例子:
     var cache = {}; function store(key, value) { cache[path.normalize(key)] = value; } store('foo/bar', 1); store('foo//baz//../bar', 2); console.log(cache); // => { "foo/bar": 2 }

    坑出没注意: 标准化之后的路径里的斜杠在Windows系统下是\,而在Linux系统下是/。如果想保证任何系统下都使用/作为路径分隔符的话,需要用.replace(/\\/g, '/')再替换一下标准路径。

  • path.join将传入的多个路径拼接为标准路径。该方法可避免手工拼接路径字符串的繁琐,并且能在不同系统下正确使用相应的路径分隔符。以下是一个例子:
     path.join('foo/', 'baz/', '../bar'); // => "foo/bar"
  • path.extname当我们需要根据不同文件扩展名做不同操作时,该方法就显得很好用。以下是一个例子:
     path.extname('foo/bar.js'); // => ".js"

path模块提供的其余方法也不多,稍微看一下官方文档就能全部掌握。

遍历目录

遍历目录是操作文件时的一个常见需求。比如写一个程序,需要找到并处理指定目录下的所有JS文件时,就需要遍历整个目录。

递归算法

遍历目录时一般使用递归算法,否则就难以编写出简洁的代码。递归算法与数学归纳法类似,通过不断缩小问题的规模来解决问题。以下示例说明了这种方法。

function factorial(n) { if (n === 1) { return 1; } else { return n * factorial(n - 1); } }

上边的函数用于计算N的阶乘(N!)。可以看到,当N大于1时,问题简化为计算N乘以N-1的阶乘。当N等于1时,问题达到最小规模,不需要再简化,因此直接返回1。

陷阱: 使用递归算法编写的代码虽然简洁,但由于每递归一次就产生一次函数调用,在需要优先考虑性能时,需要把递归算法转换为循环算法,以减少函数调用次数。

遍历算法

目录是一个树状结构,在遍历时一般使用深度优先+先序遍历算法。深度优先,意味着到达一个节点后,首先接着遍历子节点而不是邻居节点。先序遍历,意味着首次到达了某节点就算遍历完成,而不是最后一次返回某节点才算数。因此使用这种遍历方式时,下边这棵树的遍历顺序是A > B > D > E > C > F

 A / \ B C / \ \ D E F

同步遍历

了解了必要的算法后,我们可以简单地实现以下目录遍历函数。

function travel(dir, callback) { fs.readdirSync(dir).forEach(function (file) { var pathname = path.join(dir, file); if (fs.statSync(pathname).isDirectory()) { travel(pathname, callback); } else { callback(pathname); } }); }

可以看到,该函数以某个目录作为遍历的起点。遇到一个子目录时,就先接着遍历子目录。遇到一个文件时,就把文件的绝对路径传给回调函数。回调函数拿到文件路径后,就可以做各种判断和处理。因此假设有以下目录:

- /home/user/ - foo/ x.js - bar/ y.js z.css

使用以下代码遍历该目录时,得到的输入如下。

travel('/home/user', function (pathname) { console.log(pathname); }); ------------------------ /home/user/foo/x.js /home/user/bar/y.js /home/user/z.css

异步遍历

如果读取目录或读取文件状态时使用的是异步API,目录遍历函数实现起来会有些复杂,但原理完全相同。travel函数的异步版本如下。

function travel(dir, callback, finish) { fs.readdir(dir, function (err, files) { (function next(i) { if (i < files.length) { var pathname = path.join(dir, files[i]); fs.stat(pathname, function (err, stats) { if (stats.isDirectory()) { travel(pathname, callback, function () { next(i + 1); }); } else { callback(pathname, function () { next(i + 1); }); } }); } else { finish && finish(); } }(0)); }); }

这里不详细介绍异步遍历函数的编写技巧,在后续章节中会详细介绍这个。总之我们可以看到异步编程还是蛮复杂的。

文本编码

使用NodeJS编写前端工具时,操作得最多的是文本文件,因此也就涉及到了文件编码的处理问题。我们常用的文本编码有UTF8GBK两种,并且UTF8文件还可能带有BOM。在读取不同编码的文本文件时,需要将文件内容转换为JS使用的UTF8编码字符串后才能正常处理。

BOM的移除

BOM用于标记一个文本文件使用Unicode编码,其本身是一个Unicode字符(”\uFEFF”),位于文本文件头部。在不同的Unicode编码下,BOM字符对应的二进制字节如下:

 Bytes Encoding ---------------------------- FE FF UTF16BE FF FE UTF16LE EF BB BF UTF8

因此,我们可以根据文本文件头几个字节等于啥来判断文件是否包含BOM,以及使用哪种Unicode编码。但是,BOM字符虽然起到了标记文件编码的作用,其本身却不属于文件内容的一部分,如果读取文本文件时不去掉BOM,在某些使用场景下就会有问题。例如我们把几个JS文件合并成一个文件后,如果文件中间含有BOM字符,就会导致浏览器JS语法错误。因此,使用NodeJS读取文本文件时,一般需要去掉BOM。例如,以下代码实现了识别和去除UTF8 BOM的功能。

function readText(pathname) { var bin = fs.readFileSync(pathname); if (bin[0] === 0xEF && bin[1] === 0xBB && bin[2] === 0xBF) { bin = bin.slice(3); } return bin.toString('utf-8'); }

GBK转UTF8

NodeJS支持在读取文本文件时,或者在Buffer转换为字符串时指定文本编码,但遗憾的是,GBK编码不在NodeJS自身支持范围内。因此,一般我们借助iconv-lite这个三方包来转换编码。使用NPM下载该包后,我们可以按下边方式编写一个读取GBK文本文件的函数。

var iconv = require('iconv-lite'); function readGBKText(pathname) { var bin = fs.readFileSync(pathname); return iconv.decode(bin, 'gbk'); }

单字节编码

有时候,我们无法预知需要读取的文件采用哪种编码,因此也就无法指定正确的编码。比如我们要处理的某些CSS文件中,有的用GBK编码,有的用UTF8编码。虽然可以一定程度可以根据文件的字节内容猜测出文本编码,但这里要介绍的是有些局限,但是要简单得多的一种技术。

首先我们知道,如果一个文本文件只包含英文字符,比如Hello World,那无论用GBK编码或是UTF8编码读取这个文件都是没问题的。这是因为在这些编码下,ASCII0~128范围内字符都使用相同的单字节编码。

反过来讲,即使一个文本文件中有中文等字符,如果我们需要处理的字符仅在ASCII0~128范围内,比如除了注释和字符串以外的JS代码,我们就可以统一使用单字节编码来读取文件,不用关心文件的实际编码是GBK还是UTF8。以下示例说明了这种方法。

1. GBK编码源文件内容: var foo = '中文'; 2. 对应字节: 76 61 72 20 66 6F 6F 20 3D 20 27 D6 D0 CE C4 27 3B 3. 使用单字节编码读取后得到的内容: var foo = '{乱码}{乱码}{乱码}{乱码}'; 4. 替换内容: var bar = '{乱码}{乱码}{乱码}{乱码}'; 5. 使用单字节编码保存后对应字节: 76 61 72 20 62 61 72 20 3D 20 27 D6 D0 CE C4 27 3B 6. 使用GBK编码读取后得到内容: var bar = '中文';

这里的诀窍在于,不管大于0xEF的单个字节在单字节编码下被解析成什么乱码字符,使用同样的单字节编码保存这些乱码字符时,背后对应的字节保持不变。

NodeJS中自带了一种binary编码可以用来实现这个方法,因此在下例中,我们使用这种编码来演示上例对应的代码该怎么写。

function replace(pathname) { var str = fs.readFileSync(pathname, 'binary'); str = str.replace('foo', 'bar'); fs.writeFileSync(pathname, str, 'binary'); }

小结

本章介绍了使用NodeJS操作文件时需要的API以及一些技巧,总结起来有以下几点:

  • 学好文件操作,编写各种程序都不怕。
  • 如果不是很在意性能,fs模块的同步API能让生活更加美好。
  • 需要对文件读写做到字节级别的精细控制时,请使用fs模块的文件底层操作API。
  • 不要使用拼接字符串的方式来处理路径,使用path模块。
  • 掌握好目录遍历和文件编码处理技巧,很实用。

网络操作

不了解网络编程的程序员不是好前端,而NodeJS恰好提供了一扇了解网络编程的窗口。通过NodeJS,除了可以编写一些服务端程序来协助前端开发和测试外,还能够学习一些HTTP协议与Socket协议的相关知识,这些知识在优化前端性能和排查前端故障时说不定能派上用场。本章将介绍与之相关的NodeJS内置模块。

开门红

NodeJS本来的用途是编写高性能Web服务器。我们首先在这里重复一下官方文档里的例子,使用NodeJS内置的http模块简单实现一个HTTP服务器。

var http = require('http'); http.createServer(function (request, response) { response.writeHead(200, { 'Content-Type': 'text-plain' }); response.end('Hello World\n'); }).listen(8124);

以上程序创建了一个HTTP服务器并监听8124端口,打开浏览器访问该端口http://127.0.0.1:8124/就能够看到效果。

豆知识: 在Linux系统下,监听1024以下端口需要root权限。因此,如果想监听80或443端口的话,需要使用sudo命令启动程序。

API走马观花

我们先大致看看NodeJS提供了哪些和网络操作有关的API。这里并不逐一介绍每个API的使用方法,官方文档已经做得很好了。

HTTP

官方文档: http://nodejs.org/api/http.html

‘http’模块提供两种使用方式:

  • 作为服务端使用时,创建一个HTTP服务器,监听HTTP客户端请求并返回响应。
  • 作为客户端使用时,发起一个HTTP客户端请求,获取服务端响应。

首先我们来看看服务端模式下如何工作。如开门红中的例子所示,首先需要使用.createServer方法创建一个服务器,然后调用.listen方法监听端口。之后,每当来了一个客户端请求,创建服务器时传入的回调函数就被调用一次。可以看出,这是一种事件机制。

HTTP请求本质上是一个数据流,由请求头(headers)和请求体(body)组成。例如以下是一个完整的HTTP请求数据内容。

POST / HTTP/1.1 User-Agent: curl/7.26.0 Host: localhost Accept: */* Content-Length: 11 Content-Type: application/x-www-form-urlencoded Hello World

可以看到,空行之上是请求头,之下是请求体。HTTP请求在发送给服务器时,可以认为是按照从头到尾的顺序一个字节一个字节地以数据流方式发送的。而http模块创建的HTTP服务器在接收到完整的请求头后,就会调用回调函数。在回调函数中,除了可以使用request对象访问请求头数据外,还能把request对象当作一个只读数据流来访问请求体数据。以下是一个例子。

http.createServer(function (request, response) { var body = []; console.log(request.method); console.log(request.headers); request.on('data', function (chunk) { body.push(chunk); }); request.on('end', function () { body = Buffer.concat(body); console.log(body.toString()); }); }).listen(80); ------------------------------------ POST { 'user-agent': 'curl/7.26.0', host: 'localhost', accept: '*/*', 'content-length': '11', 'content-type': 'application/x-www-form-urlencoded' } Hello World

HTTP响应本质上也是一个数据流,同样由响应头(headers)和响应体(body)组成。例如以下是一个完整的HTTP请求数据内容。

HTTP/1.1 200 OK Content-Type: text/plain Content-Length: 11 Date: Tue, 05 Nov 2013 05:31:38 GMT Connection: keep-alive Hello World

在回调函数中,除了可以使用response对象来写入响应头数据外,还能把response对象当作一个只写数据流来写入响应体数据。例如在以下例子中,服务端原样将客户端请求的请求体数据返回给客户端。

http.createServer(function (request, response) { response.writeHead(200, { 'Content-Type': 'text/plain' }); request.on('data', function (chunk) { response.write(chunk); }); request.on('end', function () { response.end(); }); }).listen(80);

接下来我们看看客户端模式下如何工作。为了发起一个客户端HTTP请求,我们需要指定目标服务器的位置并发送请求头和请求体,以下示例演示了具体做法。

var options = { hostname: 'www.example.com', port: 80, path: '/upload', method: 'POST', headers: { 'Content-Type': 'application/x-www-form-urlencoded' } }; var request = http.request(options, function (response) {}); request.write('Hello World'); request.end();

可以看到,.request方法创建了一个客户端,并指定请求目标和请求头数据。之后,就可以把request对象当作一个只写数据流来写入请求体数据和结束请求。另外,由于HTTP请求中GET请求是最常见的一种,并且不需要请求体,因此http模块也提供了以下便捷API。

http.get('http://www.example.com/', function (response) {});

当客户端发送请求并接收到完整的服务端响应头时,就会调用回调函数。在回调函数中,除了可以使用response对象访问响应头数据外,还能把response对象当作一个只读数据流来访问响应体数据。以下是一个例子。

http.get('http://www.example.com/', function (response) { var body = []; console.log(response.statusCode); console.log(response.headers); response.on('data', function (chunk) { body.push(chunk); }); response.on('end', function () { body = Buffer.concat(body); console.log(body.toString()); }); }); ------------------------------------ 200 { 'content-type': 'text/html', server: 'Apache', 'content-length': '801', date: 'Tue, 05 Nov 2013 06:08:41 GMT', connection: 'keep-alive' } <!DOCTYPE html> ...

HTTPS

官方文档: http://nodejs.org/api/https.html

https模块与http模块极为类似,区别在于https模块需要额外处理SSL证书。

在服务端模式下,创建一个HTTPS服务器的示例如下。

var options = { key: fs.readFileSync('./ssl/default.key'), cert: fs.readFileSync('./ssl/default.cer') }; var server = https.createServer(options, function (request, response) { // ... });

可以看到,与创建HTTP服务器相比,多了一个options对象,通过keycert字段指定了HTTPS服务器使用的私钥和公钥。

另外,NodeJS支持SNI技术,可以根据HTTPS客户端请求使用的域名动态使用不同的证书,因此同一个HTTPS服务器可以使用多个域名提供服务。接着上例,可以使用以下方法为HTTPS服务器添加多组证书。

server.addContext('foo.com', { key: fs.readFileSync('./ssl/foo.com.key'), cert: fs.readFileSync('./ssl/foo.com.cer') }); server.addContext('bar.com', { key: fs.readFileSync('./ssl/bar.com.key'), cert: fs.readFileSync('./ssl/bar.com.cer') });

在客户端模式下,发起一个HTTPS客户端请求与http模块几乎相同,示例如下。

var options = { hostname: 'www.example.com', port: 443, path: '/', method: 'GET' }; var request = https.request(options, function (response) {}); request.end();

但如果目标服务器使用的SSL证书是自制的,不是从颁发机构购买的,默认情况下https模块会拒绝连接,提示说有证书安全问题。在options里加入rejectUnauthorized: false字段可以禁用对证书有效性的检查,从而允许https模块请求开发环境下使用自制证书的HTTPS服务器。

URL

官方文档: http://nodejs.org/api/url.html

处理HTTP请求时url模块使用率超高,因为该模块允许解析URL、生成URL,以及拼接URL。首先我们来看看一个完整的URL的各组成部分。

 href ----------------------------------------------------------------- host path --------------- ---------------------------- http: // user:pass @ host.com : 8080 /p/a/t/h ?query=string #hash ----- --------- -------- ---- -------- ------------- ----- protocol auth hostname port pathname search hash ------------ query

我们可以使用.parse方法来将一个URL字符串转换为URL对象,示例如下。

url.parse('http://user:pass@host.com:8080/p/a/t/h?query=string#hash'); /* => { protocol: 'http:', auth: 'user:pass', host: 'host.com:8080', port: '8080', hostname: 'host.com', hash: '#hash', search: '?query=string', query: 'query=string', pathname: '/p/a/t/h', path: '/p/a/t/h?query=string', href: 'http://user:pass@host.com:8080/p/a/t/h?query=string#hash' } */

传给.parse方法的不一定要是一个完整的URL,例如在HTTP服务器回调函数中,request.url不包含协议头和域名,但同样可以用.parse方法解析。

http.createServer(function (request, response) { var tmp = request.url; // => "/foo/bar?a=b" url.parse(tmp); /* => { protocol: null, slashes: null, auth: null, host: null, port: null, hostname: null, hash: null, search: '?a=b', query: 'a=b', pathname: '/foo/bar', path: '/foo/bar?a=b', href: '/foo/bar?a=b' } */ }).listen(80);

.parse方法还支持第二个和第三个布尔类型可选参数。第二个参数等于true时,该方法返回的URL对象中,query字段不再是一个字符串,而是一个经过querystring模块转换后的参数对象。第三个参数等于true时,该方法可以正确解析不带协议头的URL,例如//www.example.com/foo/bar

反过来,format方法允许将一个URL对象转换为URL字符串,示例如下。

url.format({ protocol: 'http:', host: 'www.example.com', pathname: '/p/a/t/h', search: 'query=string' }); /* => 'http://www.example.com/p/a/t/h?query=string' */

另外,.resolve方法可以用于拼接URL,示例如下。

url.resolve('http://www.example.com/foo/bar', '../baz'); /* => http://www.example.com/baz */

Query String

官方文档: http://nodejs.org/api/querystring.html

querystring模块用于实现URL参数字符串与参数对象的互相转换,示例如下。

querystring.parse('foo=bar&baz=qux&baz=quux&corge'); /* => { foo: 'bar', baz: ['qux', 'quux'], corge: '' } */ querystring.stringify({ foo: 'bar', baz: ['qux', 'quux'], corge: '' }); /* => 'foo=bar&baz=qux&baz=quux&corge=' */

Zlib

官方文档: http://nodejs.org/api/zlib.html

zlib模块提供了数据压缩和解压的功能。当我们处理HTTP请求和响应时,可能需要用到这个模块。

首先我们看一个使用zlib模块压缩HTTP响应体数据的例子。这个例子中,判断了客户端是否支持gzip,并在支持的情况下使用zlib模块返回gzip之后的响应体数据。

http.createServer(function (request, response) { var i = 1024, data = ''; while (i--) { data += '.'; } if ((request.headers['accept-encoding'] || '').indexOf('gzip') !== -1) { zlib.gzip(data, function (err, data) { response.writeHead(200, { 'Content-Type': 'text/plain', 'Content-Encoding': 'gzip' }); response.end(data); }); } else { response.writeHead(200, { 'Content-Type': 'text/plain' }); response.end(data); } }).listen(80);

接着我们看一个使用zlib模块解压HTTP响应体数据的例子。这个例子中,判断了服务端响应是否使用gzip压缩,并在压缩的情况下使用zlib模块解压响应体数据。

var options = { hostname: 'www.example.com', port: 80, path: '/', method: 'GET', headers: { 'Accept-Encoding': 'gzip, deflate' } }; http.request(options, function (response) { var body = []; response.on('data', function (chunk) { body.push(chunk); }); response.on('end', function () { body = Buffer.concat(body); if (response.headers['content-encoding'] === 'gzip') { zlib.gunzip(body, function (err, data) { console.log(data.toString()); }); } else { console.log(data.toString()); } }); }).end();

Net

官方文档: http://nodejs.org/api/net.html

net模块可用于创建Socket服务器或Socket客户端。由于Socket在前端领域的使用范围还不是很广,这里先不涉及到WebSocket的介绍,仅仅简单演示一下如何从Socket层面来实现HTTP请求和响应。

首先我们来看一个使用Socket搭建一个很不严谨的HTTP服务器的例子。这个HTTP服务器不管收到啥请求,都固定返回相同的响应。

net.createServer(function (conn) { conn.on('data', function (data) { conn.write([ 'HTTP/1.1 200 OK', 'Content-Type: text/plain', 'Content-Length: 11', '', 'Hello World' ].join('\n')); }); }).listen(80);

接着我们来看一个使用Socket发起HTTP客户端请求的例子。这个例子中,Socket客户端在建立连接后发送了一个HTTP GET请求,并通过data事件监听函数来获取服务器响应。

var options = { port: 80, host: 'www.example.com' }; var client = net.connect(options, function () { client.write([ 'GET / HTTP/1.1', 'User-Agent: curl/7.26.0', 'Host: www.baidu.com', 'Accept: */*', '', '' ].join('\n')); }); client.on('data', function (data) { console.log(data.toString()); client.end(); });

灵机一点

使用NodeJS操作网络,特别是操作HTTP请求和响应时会遇到一些惊喜,这里对一些常见问题做解答。

  • 问: 为什么通过headers对象访问到的HTTP请求头或响应头字段不是驼峰的?答: 从规范上讲,HTTP请求头和响应头字段都应该是驼峰的。但现实是残酷的,不是每个HTTP服务端或客户端程序都严格遵循规范,所以NodeJS在处理从别的客户端或服务端收到的头字段时,都统一地转换为了小写字母格式,以便开发者能使用统一的方式来访问头字段,例如headers['content-length']
  • 问: 为什么http模块创建的HTTP服务器返回的响应是chunked传输方式的?答: 因为默认情况下,使用.writeHead方法写入响应头后,允许使用.write方法写入任意长度的响应体数据,并使用.end方法结束一个响应。由于响应体数据长度不确定,因此NodeJS自动在响应头里添加了Transfer-Encoding: chunked字段,并采用chunked传输方式。但是当响应体数据长度确定时,可使用.writeHead方法在响应头里加上Content-Length字段,这样做之后NodeJS就不会自动添加Transfer-Encoding字段和使用chunked传输方式。
  • 问: 为什么使用http模块发起HTTP客户端请求时,有时候会发生socket hang up错误?答: 发起客户端HTTP请求前需要先创建一个客户端。http模块提供了一个全局客户端http.globalAgent,可以让我们使用.request.get方法时不用手动创建客户端。但是全局客户端默认只允许5个并发Socket连接,当某一个时刻HTTP客户端请求创建过多,超过这个数字时,就会发生socket hang up错误。解决方法也很简单,通过http.globalAgent.maxSockets属性把这个数字改大些即可。另外,https模块遇到这个问题时也一样通过https.globalAgent.maxSockets属性来处理。

小结

本章介绍了使用NodeJS操作网络时需要的API以及一些坑回避技巧,总结起来有以下几点:

  • httphttps模块支持服务端模式和客户端模式两种使用方式。
  • requestresponse对象除了用于读写头数据外,都可以当作数据流来操作。
  • url.parse方法加上request.url属性是处理HTTP请求时的固定搭配。
  • 使用zlib模块可以减少使用HTTP协议时的数据传输量。
  • 通过net模块的Socket服务器与客户端可对HTTP协议做底层操作。
  • 小心踩坑。

进程管理

NodeJS可以感知和控制自身进程的运行环境和状态,也可以创建子进程并与其协同工作,这使得NodeJS可以把多个程序组合在一起共同完成某项工作,并在其中充当胶水和调度器的作用。本章除了介绍与之相关的NodeJS内置模块外,还会重点介绍典型的使用场景。

开门红

我们已经知道了NodeJS自带的fs模块比较基础,把一个目录里的所有文件和子目录都拷贝到另一个目录里需要写不少代码。另外我们也知道,终端下的cp命令比较好用,一条cp -r source/* target命令就能搞定目录拷贝。那我们首先看看如何使用NodeJS调用终端命令来简化目录拷贝,示例代码如下:

var child_process = require('child_process'); var util = require('util'); function copy(source, target, callback) { child_process.exec( util.format('cp -r %s/* %s', source, target), callback); } copy('a', 'b', function (err) { // ... });

从以上代码中可以看到,子进程是异步运行的,通过回调函数返回执行结果。

API走马观花

我们先大致看看NodeJS提供了哪些和进程管理有关的API。这里并不逐一介绍每个API的使用方法,官方文档已经做得很好了。

Process

官方文档: http://nodejs.org/api/process.html

任何一个进程都有启动进程时使用的命令行参数,有标准输入标准输出,有运行权限,有运行环境和运行状态。在NodeJS中,可以通过process对象感知和控制NodeJS自身进程的方方面面。另外需要注意的是,process不是内置模块,而是一个全局对象,因此在任何地方都可以直接使用。

Child Process

官方文档: http://nodejs.org/api/child_process.html

使用child_process模块可以创建和控制子进程。该模块提供的API中最核心的是.spawn,其余API都是针对特定使用场景对它的进一步封装,算是一种语法糖。

Cluster

官方文档: http://nodejs.org/api/cluster.html

cluster模块是对child_process模块的进一步封装,专用于解决单进程NodeJS Web服务器无法充分利用多核CPU的问题。使用该模块可以简化多进程服务器程序的开发,让每个核上运行一个工作进程,并统一通过主进程监听端口和分发请求。

应用场景

和进程管理相关的API单独介绍起来比较枯燥,因此这里从一些典型的应用场景出发,分别介绍一些重要API的使用方法。

如何获取命令行参数

在NodeJS中可以通过process.argv获取命令行参数。但是比较意外的是,node执行程序路径和主模块文件路径固定占据了argv[0]argv[1]两个位置,而第一个命令行参数从argv[2]开始。为了让argv使用起来更加自然,可以按照以下方式处理。

function main(argv) { // ... } main(process.argv.slice(2));

如何退出程序

通常一个程序做完所有事情后就正常退出了,这时程序的退出状态码为0。或者一个程序运行时发生了异常后就挂了,这时程序的退出状态码不等于0。如果我们在代码中捕获了某个异常,但是觉得程序不应该继续运行下去,需要立即退出,并且需要把退出状态码设置为指定数字,比如1,就可以按照以下方式:

try { // ... } catch (err) { // ... process.exit(1); }

如何控制输入输出

NodeJS程序的标准输入流(stdin)、一个标准输出流(stdout)、一个标准错误流(stderr)分别对应process.stdinprocess.stdoutprocess.stderr,第一个是只读数据流,后边两个是只写数据流,对它们的操作按照对数据流的操作方式即可。例如,console.log可以按照以下方式实现。

function log() { process.stdout.write( util.format.apply(util, arguments) + '\n'); }

如何降权

在Linux系统下,我们知道需要使用root权限才能监听1024以下端口。但是一旦完成端口监听后,继续让程序运行在root权限下存在安全隐患,因此最好能把权限降下来。以下是这样一个例子。

http.createServer(callback).listen(80, function () { var env = process.env, uid = parseInt(env['SUDO_UID'] || process.getuid(), 10), gid = parseInt(env['SUDO_GID'] || process.getgid(), 10); process.setgid(gid); process.setuid(uid); });

上例中有几点需要注意:

  1. 如果是通过sudo获取root权限的,运行程序的用户的UID和GID保存在环境变量SUDO_UIDSUDO_GID里边。如果是通过chmod +s方式获取root权限的,运行程序的用户的UID和GID可直接通过process.getuidprocess.getgid方法获取。
  2. process.setuidprocess.setgid方法只接受number类型的参数。
  3. 降权时必须先降GID再降UID,否则顺序反过来的话就没权限更改程序的GID了。

如何创建子进程

以下是一个创建NodeJS子进程的例子。

var child = child_process.spawn('node', [ 'xxx.js' ]); child.stdout.on('data', function (data) { console.log('stdout: ' + data); }); child.stderr.on('data', function (data) { console.log('stderr: ' + data); }); child.on('close', function (code) { console.log('child process exited with code ' + code); });

上例中使用了.spawn(exec, args, options)方法,该方法支持三个参数。第一个参数是执行文件路径,可以是执行文件的相对或绝对路径,也可以是根据PATH环境变量能找到的执行文件名。第二个参数中,数组中的每个成员都按顺序对应一个命令行参数。第三个参数可选,用于配置子进程的执行环境与行为。

另外,上例中虽然通过子进程对象的.stdout.stderr访问子进程的输出,但通过options.stdio字段的不同配置,可以将子进程的输入输出重定向到任何数据流上,或者让子进程共享父进程的标准输入输出流,或者直接忽略子进程的输入输出。

进程间如何通讯

在Linux系统下,进程之间可以通过信号互相通信。以下是一个例子。

/* parent.js */ var child = child_process.spawn('node', [ 'child.js' ]); child.kill('SIGTERM'); /* child.js */ process.on('SIGTERM', function () { cleanUp(); process.exit(0); });

在上例中,父进程通过.kill方法向子进程发送SIGTERM信号,子进程监听process对象的SIGTERM事件响应信号。不要被.kill方法的名称迷惑了,该方法本质上是用来给进程发送信号的,进程收到信号后具体要做啥,完全取决于信号的种类和进程自身的代码。

另外,如果父子进程都是NodeJS进程,就可以通过IPC(进程间通讯)双向传递数据。以下是一个例子。

/* parent.js */ var child = child_process.spawn('node', [ 'child.js' ], { stdio: [ 0, 1, 2, 'ipc' ] }); child.on('message', function (msg) { console.log(msg); }); child.send({ hello: 'hello' }); /* child.js */ process.on('message', function (msg) { msg.hello = msg.hello.toUpperCase(); process.send(msg); });

可以看到,父进程在创建子进程时,在options.stdio字段中通过ipc开启了一条IPC通道,之后就可以监听子进程对象的message事件接收来自子进程的消息,并通过.send方法给子进程发送消息。在子进程这边,可以在process对象上监听message事件接收来自父进程的消息,并通过.send方法向父进程发送消息。数据在传递过程中,会先在发送端使用JSON.stringify方法序列化,再在接收端使用JSON.parse方法反序列化。

如何守护子进程

守护进程一般用于监控工作进程的运行状态,在工作进程不正常退出时重启工作进程,保障工作进程不间断运行。以下是一种实现方式。

/* daemon.js */ function spawn(mainModule) { var worker = child_process.spawn('node', [ mainModule ]); worker.on('exit', function (code) { if (code !== 0) { spawn(mainModule); } }); } spawn('worker.js');

可以看到,工作进程非正常退出时,守护进程立即重启工作进程。

小结

本章介绍了使用NodeJS管理进程时需要的API以及主要的应用场景,总结起来有以下几点:

  • 使用process对象管理自身。
  • 使用child_process模块创建和管理子进程。

异步编程

NodeJS最大的卖点——事件机制和异步IO,对开发者并不是透明的。开发者需要按异步方式编写代码才用得上这个卖点,而这一点也遭到了一些NodeJS反对者的抨击。但不管怎样,异步编程确实是NodeJS最大的特点,没有掌握异步编程就不能说是真正学会了NodeJS。本章将介绍与异步编程相关的各种知识。

回调

在代码中,异步编程的直接体现就是回调。异步编程依托于回调来实现,但不能说使用了回调后程序就异步化了。我们首先可以看看以下代码。

function heavyCompute(n, callback) { var count = 0, i, j; for (i = n; i > 0; --i) { for (j = n; j > 0; --j) { count += 1; } } callback(count); } heavyCompute(10000, function (count) { console.log(count); }); console.log('hello'); -- Console ------------------------------ 100000000 hello

可以看到,以上代码中的回调函数仍然先于后续代码执行。JS本身是单线程运行的,不可能在一段代码还未结束运行时去运行别的代码,因此也就不存在异步执行的概念。

但是,如果某个函数做的事情是创建一个别的线程或进程,并与JS主线程并行地做一些事情,并在事情做完后通知JS主线程,那情况又不一样了。我们接着看看以下代码。

setTimeout(function () { console.log('world'); }, 1000); console.log('hello'); -- Console ------------------------------ hello world

这次可以看到,回调函数后于后续代码执行了。如同上边所说,JS本身是单线程的,无法异步执行,因此我们可以认为setTimeout这类JS规范之外的由运行环境提供的特殊函数做的事情是创建一个平行线程后立即返回,让JS主进程可以接着执行后续代码,并在收到平行进程的通知后再执行回调函数。除了setTimeoutsetInterval这些常见的,这类函数还包括NodeJS提供的诸如fs.readFile之类的异步API。

另外,我们仍然回到JS是单线程运行的这个事实上,这决定了JS在执行完一段代码之前无法执行包括回调函数在内的别的代码。也就是说,即使平行线程完成工作了,通知JS主线程执行回调函数了,回调函数也要等到JS主线程空闲时才能开始执行。以下就是这么一个例子。

function heavyCompute(n) { var count = 0, i, j; for (i = n; i > 0; --i) { for (j = n; j > 0; --j) { count += 1; } } } var t = new Date(); setTimeout(function () { console.log(new Date() - t); }, 1000); heavyCompute(50000); -- Console ------------------------------ 8520

可以看到,本来应该在1秒后被调用的回调函数因为JS主线程忙于运行其它代码,实际执行时间被大幅延迟。

代码设计模式

异步编程有很多特有的代码设计模式,为了实现同样的功能,使用同步方式和异步方式编写的代码会有很大差异。以下分别介绍一些常见的模式。

函数返回值

使用一个函数的输出作为另一个函数的输入是很常见的需求,在同步方式下一般按以下方式编写代码:

var output = fn1(fn2('input')); // Do something.

而在异步方式下,由于函数执行结果不是通过返回值,而是通过回调函数传递,因此一般按以下方式编写代码:

fn2('input', function (output2) { fn1(output2, function (output1) { // Do something. }); });

可以看到,这种方式就是一个回调函数套一个回调函多,套得太多了很容易写出>形状的代码。

遍历数组

在遍历数组时,使用某个函数依次对数据成员做一些处理也是常见的需求。如果函数是同步执行的,一般就会写出以下代码:

var len = arr.length, i = 0; for (; i < len; ++i) { arr[i] = sync(arr[i]); } // All array items have processed.

如果函数是异步执行的,以上代码就无法保证循环结束后所有数组成员都处理完毕了。如果数组成员必须一个接一个串行处理,则一般按照以下方式编写异步代码:

(function next(i, len, callback) { if (i < len) { async(arr[i], function (value) { arr[i] = value; next(i + 1, len, callback); }); } else { callback(); } }(0, arr.length, function () { // All array items have processed. }));

可以看到,以上代码在异步函数执行一次并返回执行结果后才传入下一个数组成员并开始下一轮执行,直到所有数组成员处理完毕后,通过回调的方式触发后续代码的执行。

如果数组成员可以并行处理,但后续代码仍然需要所有数组成员处理完毕后才能执行的话,则异步代码会调整成以下形式:

(function (i, len, count, callback) { for (; i < len; ++i) { (function (i) { async(arr[i], function (value) { arr[i] = value; if (++count === len) { callback(); } }); }(i)); } }(0, arr.length, 0, function () { // All array items have processed. }));

可以看到,与异步串行遍历的版本相比,以上代码并行处理所有数组成员,并通过计数器变量来判断什么时候所有数组成员都处理完毕了。

异常处理

JS自身提供的异常捕获和处理机制——try..catch..,只能用于同步执行的代码。以下是一个例子。

function sync(fn) { return fn(); } try { sync(null); // Do something. } catch (err) { console.log('Error: %s', err.message); } -- Console ------------------------------ Error: object is not a function

可以看到,异常会沿着代码执行路径一直冒泡,直到遇到第一个try语句时被捕获住。但由于异步函数会打断代码执行路径,异步函数执行过程中以及执行之后产生的异常冒泡到执行路径被打断的位置时,如果一直没有遇到try语句,就作为一个全局异常抛出。以下是一个例子。

function async(fn, callback) { // Code execution path breaks here. setTimeout(function () { callback(fn()); }, 0); } try { async(null, function (data) { // Do something. }); } catch (err) { console.log('Error: %s', err.message); } -- Console ------------------------------ /home/user/test.js:4 callback(fn()); ^ TypeError: object is not a function at null._onTimeout (/home/user/test.js:4:13) at Timer.listOnTimeout [as ontimeout] (timers.js:110:15)

因为代码执行路径被打断了,我们就需要在异常冒泡到断点之前用try语句把异常捕获住,并通过回调函数传递被捕获的异常。于是我们可以像下边这样改造上边的例子。

function async(fn, callback) { // Code execution path breaks here. setTimeout(function () { try { callback(null, fn()); } catch (err) { callback(err); } }, 0); } async(null, function (err, data) { if (err) { console.log('Error: %s', err.message); } else { // Do something. } }); -- Console ------------------------------ Error: object is not a function

可以看到,异常再次被捕获住了。在NodeJS中,几乎所有异步API都按照以上方式设计,回调函数中第一个参数都是err。因此我们在编写自己的异步函数时,也可以按照这种方式来处理异常,与NodeJS的设计风格保持一致。

有了异常处理方式后,我们接着可以想一想一般我们是怎么写代码的。基本上,我们的代码都是做一些事情,然后调用一个函数,然后再做一些事情,然后再调用一个函数,如此循环。如果我们写的是同步代码,只需要在代码入口点写一个try语句就能捕获所有冒泡上来的异常,示例如下。

function main() { // Do something. syncA(); // Do something. syncB(); // Do something. syncC(); } try { main(); } catch (err) { // Deal with exception. }

但是,如果我们写的是异步代码,就只有呵呵了。由于每次异步函数调用都会打断代码执行路径,只能通过回调函数来传递异常,于是我们就需要在每个回调函数里判断是否有异常发生,于是只用三次异步函数调用,就会产生下边这种代码。

function main(callback) { // Do something. asyncA(function (err, data) { if (err) { callback(err); } else { // Do something asyncB(function (err, data) { if (err) { callback(err); } else { // Do something asyncC(function (err, data) { if (err) { callback(err); } else { // Do something callback(null); } }); } }); } }); } main(function (err) { if (err) { // Deal with exception. } });

可以看到,回调函数已经让代码变得复杂了,而异步方式下对异常的处理更加剧了代码的复杂度。如果NodeJS的最大卖点最后变成这个样子,那就没人愿意用NodeJS了,因此接下来会介绍NodeJS提供的一些解决方案。

域(Domain)

官方文档: http://nodejs.org/api/domain.html

NodeJS提供了domain模块,可以简化异步代码的异常处理。在介绍该模块之前,我们需要首先理解“域”的概念。简单的讲,一个域就是一个JS运行环境,在一个运行环境中,如果一个异常没有被捕获,将作为一个全局异常被抛出。NodeJS通过process对象提供了捕获全局异常的方法,示例代码如下

process.on('uncaughtException', function (err) { console.log('Error: %s', err.message); }); setTimeout(function (fn) { fn(); }); -- Console ------------------------------ Error: undefined is not a function

虽然全局异常有个地方可以捕获了,但是对于大多数异常,我们希望尽早捕获,并根据结果决定代码的执行路径。我们用以下HTTP服务器代码作为例子:

function async(request, callback) { // Do something. asyncA(request, function (err, data) { if (err) { callback(err); } else { // Do something asyncB(request, function (err, data) { if (err) { callback(err); } else { // Do something asyncC(request, function (err, data) { if (err) { callback(err); } else { // Do something callback(null, data); } }); } }); } }); } http.createServer(function (request, response) { async(request, function (err, data) { if (err) { response.writeHead(500); response.end(); } else { response.writeHead(200); response.end(data); } }); });

以上代码将请求对象交给异步函数处理后,再根据处理结果返回响应。这里采用了使用回调函数传递异常的方案,因此async函数内部如果再多几个异步函数调用的话,代码就变成上边这副鬼样子了。为了让代码好看点,我们可以在每处理一个请求时,使用domain模块创建一个子域(JS子运行环境)。在子域内运行的代码可以随意抛出异常,而这些异常可以通过子域对象的error事件统一捕获。于是以上代码可以做如下改造:

function async(request, callback) { // Do something. asyncA(request, function (data) { // Do something asyncB(request, function (data) { // Do something asyncC(request, function (data) { // Do something callback(data); }); }); }); } http.createServer(function (request, response) { var d = domain.create(); d.on('error', function () { response.writeHead(500); response.end(); }); d.run(function () { async(request, function (data) { response.writeHead(200); response.end(data); }); }); });

可以看到,我们使用.create方法创建了一个子域对象,并通过.run方法进入需要在子域中运行的代码的入口点。而位于子域中的异步函数回调函数由于不再需要捕获异常,代码一下子瘦身很多。

陷阱

无论是通过process对象的uncaughtException事件捕获到全局异常,还是通过子域对象的error事件捕获到了子域异常,在NodeJS官方文档里都强烈建议处理完异常后立即重启程序,而不是让程序继续运行。按照官方文档的说法,发生异常后的程序处于一个不确定的运行状态,如果不立即退出的话,程序可能会发生严重内存泄漏,也可能表现得很奇怪。

但这里需要澄清一些事实。JS本身的throw..try..catch异常处理机制并不会导致内存泄漏,也不会让程序的执行结果出乎意料,但NodeJS并不是存粹的JS。NodeJS里大量的API内部是用C/C++实现的,因此NodeJS程序的运行过程中,代码执行路径穿梭于JS引擎内部和外部,而JS的异常抛出机制可能会打断正常的代码执行流程,导致C/C++部分的代码表现异常,进而导致内存泄漏等问题。

因此,使用uncaughtExceptiondomain捕获异常,代码执行路径里涉及到了C/C++部分的代码时,如果不能确定是否会导致内存泄漏等问题,最好在处理完异常后重启程序比较妥当。而使用try语句捕获异常时一般捕获到的都是JS本身的异常,不用担心上诉问题。

小结

本章介绍了JS异步编程相关的知识,总结起来有以下几点:

  • 不掌握异步编程就不算学会NodeJS。
  • 异步编程依托于回调来实现,而使用回调不一定就是异步编程。
  • 异步编程下的函数间数据传递、数组遍历和异常处理与同步编程有很大差别。
  • 使用domain模块简化异步代码的异常处理,并小心陷阱。

大示例

学习讲究的是学以致用和融会贯通。至此我们已经分别介绍了NodeJS的很多知识点,本章作为最后一章,将完整地介绍一个使用NodeJS开发Web服务器的示例。

需求

我们要开发的是一个简单的静态文件合并服务器,该服务器需要支持类似以下格式的JS或CSS文件合并请求。

http://assets.example.com/foo/??bar.js,baz.js

在以上URL中,??是一个分隔符,之前是需要合并的多个文件的URL的公共部分,之后是使用,分隔的差异部分。因此服务器处理这个URL时,返回的是以下两个文件按顺序合并后的内容。

/foo/bar.js /foo/baz.js

另外,服务器也需要能支持类似以下格式的普通的JS或CSS文件请求。

http://assets.example.com/foo/bar.js

以上就是整个需求。

第一次迭代

快速迭代是一种不错的开发方式,因此我们在第一次迭代时先实现服务器的基本功能。

设计

简单分析了需求之后,我们大致会得到以下的设计方案。

 +---------+ +-----------+ +----------+ request -->| parse |-->| combine |-->| output |--> response +---------+ +-----------+ +----------+

也就是说,服务器会首先分析URL,得到请求的文件的路径和类型(MIME)。然后,服务器会读取请求的文件,并按顺序合并文件内容。最后,服务器返回响应,完成对一次请求的处理。

另外,服务器在读取文件时需要有个根目录,并且服务器监听的HTTP端口最好也不要写死在代码里,因此服务器需要是可配置的。

实现

根据以上设计,我们写出了第一版代码如下。

var fs = require('fs'), path = require('path'), http = require('http'); var MIME = { '.css': 'text/css', '.js': 'application/javascript' }; function combineFiles(pathnames, callback) { var output = []; (function next(i, len) { if (i < len) { fs.readFile(pathnames[i], function (err, data) { if (err) { callback(err); } else { output.push(data); next(i + 1, len); } }); } else { callback(null, Buffer.concat(output)); } }(0, pathnames.length)); } function main(argv) { var config = JSON.parse(fs.readFileSync(argv[0], 'utf-8')), root = config.root || '.', port = config.port || 80; http.createServer(function (request, response) { var urlInfo = parseURL(root, request.url); combineFiles(urlInfo.pathnames, function (err, data) { if (err) { response.writeHead(404); response.end(err.message); } else { response.writeHead(200, { 'Content-Type': urlInfo.mime }); response.end(data); } }); }).listen(port); } function parseURL(root, url) { var base, pathnames, parts; if (url.indexOf('??') === -1) { url = url.replace('/', '/??'); } parts = url.split('??'); base = parts[0]; pathnames = parts[1].split(',').map(function (value) { return path.join(root, base, value); }); return { mime: MIME[path.extname(pathnames[0])] || 'text/plain', pathnames: pathnames }; } main(process.argv.slice(2));

以上代码完整实现了服务器所需的功能,并且有以下几点值得注意:

  1. 使用命令行参数传递JSON配置文件路径,入口函数负责读取配置并创建服务器。
  2. 入口函数完整描述了程序的运行逻辑,其中解析URL和合并文件的具体实现封装在其它两个函数里。
  3. 解析URL时先将普通URL转换为了文件合并URL,使得两种URL的处理方式可以一致。
  4. 合并文件时使用异步API读取文件,避免服务器因等待磁盘IO而发生阻塞。

我们可以把以上代码保存为server.js,之后就可以通过node server.js config.json命令启动程序,于是我们的第一版静态文件合并服务器就顺利完工了。

另外,以上代码存在一个不那么明显的逻辑缺陷。例如,使用以下URL请求服务器时会有惊喜。

 http://assets.example.com/foo/bar.js,foo/baz.js

经过分析之后我们会发现问题出在/被自动替换/??这个行为上,而这个问题我们可以到第二次迭代时再解决。

第二次迭代

在第一次迭代之后,我们已经有了一个可工作的版本,满足了功能需求。接下来我们需要从性能的角度出发,看看代码还有哪些改进余地。

设计

map方法换成for循环或许会更快一些,但第一版代码最大的性能问题存在于从读取文件到输出响应的过程当中。我们以处理/??a.js,b.js,c.js这个请求为例,看看整个处理过程中耗时在哪儿。

 发送请求 等待服务端响应 接收响应 ---------+----------------------+-------------> -- 解析请求 ------ 读取a.js ------ 读取b.js ------ 读取c.js -- 合并数据 -- 输出响应

可以看到,第一版代码依次把请求的文件读取到内存中之后,再合并数据和输出响应。这会导致以下两个问题:

  1. 当请求的文件比较多比较大时,串行读取文件会比较耗时,从而拉长了服务端响应等待时间。
  2. 由于每次响应输出的数据都需要先完整地缓存在内存里,当服务器请求并发数较大时,会有较大的内存开销。

对于第一个问题,很容易想到把读取文件的方式从串行改为并行。但是别这样做,因为对于机械磁盘而言,因为只有一个磁头,尝试并行读取文件只会造成磁头频繁抖动,反而降低IO效率。而对于固态硬盘,虽然的确存在多个并行IO通道,但是对于服务器并行处理的多个请求而言,硬盘已经在做并行IO了,对单个请求采用并行IO无异于拆东墙补西墙。因此,正确的做法不是改用并行IO,而是一边读取文件一边输出响应,把响应输出时机提前至读取第一个文件的时刻。这样调整后,整个请求处理过程变成下边这样。

发送请求 等待服务端响应 接收响应 ---------+----+-------------------------------> -- 解析请求 -- 检查文件是否存在 -- 输出响应头 ------ 读取和输出a.js ------ 读取和输出b.js ------ 读取和输出c.js

按上述方式解决第一个问题后,因为服务器不需要完整地缓存每个请求的输出数据了,第二个问题也迎刃而解。

实现

根据以上设计,第二版代码按以下方式调整了部分函数。

function main(argv) { var config = JSON.parse(fs.readFileSync(argv[0], 'utf-8')), root = config.root || '.', port = config.port || 80; http.createServer(function (request, response) { var urlInfo = parseURL(root, request.url); validateFiles(urlInfo.pathnames, function (err, pathnames) { if (err) { response.writeHead(404); response.end(err.message); } else { response.writeHead(200, { 'Content-Type': urlInfo.mime }); outputFiles(pathnames, response); } }); }).listen(port); } function outputFiles(pathnames, writer) { (function next(i, len) { if (i < len) { var reader = fs.createReadStream(pathnames[i]); reader.pipe(writer, { end: false }); reader.on('end', function() { next(i + 1, len); }); } else { writer.end(); } }(0, pathnames.length)); } function validateFiles(pathnames, callback) { (function next(i, len) { if (i < len) { fs.stat(pathnames[i], function (err, stats) { if (err) { callback(err); } else if (!stats.isFile()) { callback(new Error()); } else { next(i + 1, len); } }); } else { callback(null, pathnames); } }(0, pathnames.length)); }

可以看到,第二版代码在检查了请求的所有文件是否有效之后,立即就输出了响应头,并接着一边按顺序读取文件一边输出响应内容。并且,在读取文件时,第二版代码直接使用了只读数据流来简化代码。

第三次迭代

第二次迭代之后,服务器本身的功能和性能已经得到了初步满足。接下来我们需要从稳定性的角度重新审视一下代码,看看还需要做些什么。

设计

从工程角度上讲,没有绝对可靠的系统。即使第二次迭代的代码经过反复检查后能确保没有bug,也很难说是否会因为NodeJS本身,或者是操作系统本身,甚至是硬件本身导致我们的服务器程序在某一天挂掉。因此一般生产环境下的服务器程序都配有一个守护进程,在服务挂掉的时候立即重启服务。一般守护进程的代码会远比服务进程的代码简单,从概率上可以保证守护进程更难挂掉。如果再做得严谨一些,甚至守护进程自身可以在自己挂掉时重启自己,从而实现双保险。

因此在本次迭代时,我们先利用NodeJS的进程管理机制,将守护进程作为父进程,将服务器程序作为子进程,并让父进程监控子进程的运行状态,在其异常退出时重启子进程。

实现

根据以上设计,我们编写了守护进程需要的代码。

var cp = require('child_process'); var worker; function spawn(server, config) { worker = cp.spawn('node', [ server, config ]); worker.on('exit', function (code) { if (code !== 0) { spawn(server, config); } }); } function main(argv) { spawn('server.js', argv[0]); process.on('SIGTERM', function () { worker.kill(); process.exit(0); }); } main(process.argv.slice(2));

此外,服务器代码本身的入口函数也要做以下调整。

function main(argv) { var config = JSON.parse(fs.readFileSync(argv[0], 'utf-8')), root = config.root || '.', port = config.port || 80, server; server = http.createServer(function (request, response) { ... }).listen(port); process.on('SIGTERM', function () { server.close(function () { process.exit(0); }); }); }

我们可以把守护进程的代码保存为daemon.js,之后我们可以通过node daemon.js config.json启动服务,而守护进程会进一步启动和监控服务器进程。此外,为了能够正常终止服务,我们让守护进程在接收到SIGTERM信号时终止服务器进程。而在服务器进程这一端,同样在收到SIGTERM信号时先停掉HTTP服务再正常退出。至此,我们的服务器程序就靠谱很多了。

第四次迭代

在我们解决了服务器本身的功能、性能和可靠性的问题后,接着我们需要考虑一下代码部署的问题,以及服务器控制的问题。

设计

一般而言,程序在服务器上有一个固定的部署目录,每次程序有更新后,都重新发布到部署目录里。而一旦完成部署后,一般也可以通过固定的服务控制脚本启动和停止服务。因此我们的服务器程序部署目录可以做如下设计。

- deploy/ - bin/ startws.sh killws.sh + conf/ config.json + lib/ daemon.js server.js

在以上目录结构中,我们分类存放了服务控制脚本、配置文件和服务器代码。

实现

按以上目录结构分别存放对应的文件之后,接下来我们看看控制脚本怎么写。首先是start.sh

#!/bin/sh if [ ! -f "pid" ] then node ../lib/daemon.js ../conf/config.json & echo $! > pid fi

然后是killws.sh

#!/bin/sh if [ -f "pid" ] then kill $(tr -d '\r\n' < pid) rm pid fi

于是这样我们就有了一个简单的代码部署目录和服务控制脚本,我们的服务器程序就可以上线工作了。

后续迭代

我们的服务器程序正式上线工作后,我们接下来或许会发现还有很多可以改进的点。比如服务器程序在合并JS文件时可以自动在JS文件之间插入一个;来避免一些语法问题,比如服务器程序需要提供日志来统计访问量,比如服务器程序需要能充分利用多核CPU,等等。而此时的你,在学习了这么久NodeJS之后,应该已经知道该怎么做了。

小结

本章将之前零散介绍的知识点串了起来,完整地演示了一个使用NodeJS开发程序的例子,至此我们的课程就全部结束了。以下是对新诞生的NodeJSer的一些建议。

  • 要熟悉官方API文档。并不是说要熟悉到能记住每个API的名称和用法,而是要熟悉NodeJS提供了哪些功能,一旦需要时知道查询API文档的哪块地方。
  • 要先设计再实现。在开发一个程序前首先要有一个全局的设计,不一定要很周全,但要足够能写出一些代码。
  • 要实现后再设计。在写了一些代码,有了一些具体的东西后,一定会发现一些之前忽略掉的细节。这时再反过来改进之前的设计,为第二轮迭代做准备。
  • 要充分利用三方包。NodeJS有一个庞大的生态圈,在写代码之前先看看有没有现成的三方包能节省不少时间。
  • 不要迷信三方包。任何事情做过头了就不好了,三方包也是一样。三方包是一个黑盒,每多使用一个三方包,就为程序增加了一份潜在风险。并且三方包很难恰好只提供程序需要的功能,每多使用一个三方包,就让程序更加臃肿一些。因此在决定使用某个三方包之前,最好三思而后行。

from:http://nqdeng.github.io/7-days-nodejs

康托尔、哥德尔、图灵——永恒的金色对角线

我看到了它,却不敢相信它[1]
——康托尔
计算机是数学家一次失败思考的产物。
——无名氏
哥德尔不完备性定理震撼了20世纪数学界的天空,其数学意义颠覆了希尔伯特的形式化数学的宏伟计划,其哲学意义直到21世纪的今天仍然不断被延伸到各个自然学科,深刻影响着人们的思维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型,进而作出了可计算理论和现代计算机的奠基性工作,著名的停机问题给出了机械计算模型的能力极限,其深刻的意义和漂亮的证明使它成为可计算理论中的标志性定理之一。丘齐,跟图灵同时代的天才,则从另一个抽象角度提出了lambda算子的思想,与图灵机抽象的倾向于硬件性不同,丘齐的lambda算子理论是从数学的角度进行抽象,不关心运算的机械过程而只关心运算的抽象性质,只用最简洁的几条公理便建立起了与图灵机完全等价的计算模型,其体现出来的数学抽象美开出了函数式编程语言这朵奇葩,LispSchemeHaskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学界,虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主流的编程语言[2],然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中…
然而,这一切的一切,看似不很相关却又有点相关,认真思考其关系却又有点一头雾水的背后,其实隐隐藏着一条线,这条线把它们从本质上串到了一起,而顺着时光的河流逆流而上,我们将会看到,这条线的尽头,不是别人,正是只手拨开被不严密性问题困扰的19世纪数学界阴沉天空的天才数学家康托尔,康托尔创造性地将一一对应和对角线方法运用到无穷集合理论的建立当中,这个被希尔伯特称为“谁也无法将我们从康托尔为我们创造的乐园中驱逐出去”、被罗素称为“19世纪最伟大的智者之一”的人,他在集合论方面的工作终于驱散了不严密性问题带来的阴霾,仿佛一道金色的阳光刺破乌云,19世纪的数学终于看到了真正严格化的曙光,数学终于得以站在了前所未有的坚固的基础之上;集合论至今仍是数学里最基础和最重要的理论之一。而康托尔当初在研究无穷集合时最具天才的方法之一——对角线方法——则带来了极其深远的影响,其纯粹而直指事物本质的思想如洪钟大吕般响彻数学和哲学的每一个角落[3]。随着本文的展开,你将会看到,刚才提到的一切,歌德尔的不完备性定理,图灵的停机问题,lambda算子理论中神奇的Y combinator、乃至著名的罗素悖论、理发师悖论等等,其实都源自这个简洁、纯粹而同时又是最优美的数学方法,反过来说,从康托尔的对角线方法出发,我们可以轻而易举地推导出哥德尔的不完备性定理,而由后者又可以轻易导出停机问题和Y combinator,实际上,我们将会看到,后两者也可以直接由康托尔的对角线方法导出。尤其是Y combinator,这个形式上绕来绕去,本质上捉摸不透,看上去神秘莫测的算子,其实只是一个非常自然而然的推论,如果从哥德尔的不完备性定理出发,它甚至比停机问题还要来得直接简单。总之,你将会看到这些看似深奥的理论是如何由一个至为简单而又至为深刻的数学方法得出的,你将会看到最纯粹的数学美。
图灵的停机问题(The Halting Problem)
了解停机问题的可以直接跳过这一节,到下一节“Y Combinator”,了解后者的再跳到下一节“哥德尔的不完备性定理”
我们还是从图灵著名的停机问题说起,一来它相对来说是我们要说的几个定理当中最简单的,二来它也最贴近程序员。实际上,我以前曾写过一篇关于图灵机的文章,有兴趣的读者可以从那篇开始,那篇主要是从理论上阐述,所以这里我们打算避开抽象的理论,换一种符合程序员思维习惯的直观方式来加以解释。
停机问题
不存在这样一个程序(算法),它能够计算任何程序(算法)在给定输入上是否会结束(停机)。
那么,如何来证明这个停机问题呢?反证。假设我们某一天真做出了这么一个极度聪明的万能算法(就叫God_algo吧),你只要给它一段程序(二进制描述),再给它这段程序的输入,它就能告诉你这段程序在这个输入上会不会结束(停机),我们来编写一下我们的这个算法吧:
bool God_algo(char* program, char* input)
{
if(<programhalts on <input>)
return true;
return false;
}
这里我们假设if的判断语句里面是你天才思考的结晶,它能够像上帝一样洞察一切程序的宿命。现在,我们从这个God_algo出发导出一个新的算法:
bool Satan_algo(char* program)
{
if( God_algo(program, program) ){
   while(1); // loop forever!
   return false; // can never get here!
}
else
   return true;
}
正如它的名字所暗示的那样,这个算法便是一切邪恶的根源了。当我们把这个算法运用到它自身身上时,会发生什么呢?
Satan_algo(Satan_algo);
我们来分析一下这行简单的调用:
显然,Satan_algo(Satan_algo)这个调用要么能够运行结束返回(停机),要么不能返回(loop forever)。
如果它能够结束,那么Santa_algo算法里面的那个if判断就会成立(因为God_algo(Santa_algo,Santa_algo)将会返回true),从而程序便进入那个包含一个无穷循环while(1);的if分支,于是这个Satan_algo(Satan_algo)调用便永远不会返回(结束)了
如果Satan_algo(Satan_algo)不能结束(停机)呢,则if判断就会失败,从而选择另一个if分支并返回true,即Satan_algo(Satan_algo)能够返回(停机)
总之,我们有:
Satan_algo(Satan_algo)能够停机=> 它不能停机
Satan_algo(Satan_algo)不能停机=> 它能够停机
所以它停也不是,不停也不是。左右矛盾。
于是,我们的假设,即God_algo算法的存在性,便不成立了。正如拉格朗日所说:“陛下,我们不需要(上帝)这个假设”[4]
这个证明相信每个程序员都能够容易的看懂。然而,这个看似不可捉摸的技巧背后其实隐藏着深刻的数学原理(甚至是哲学原理)。在没有认识到这一数学原理之前,至少我当时是对于图灵如何想出这一绝妙证明感到无法理解。但后面,在介绍完了与图灵的停机问题“同构”的Y combinator之后,我们会深入哥德尔的不完备性定理,在理解了哥德尔不完备性定理之后,我们从这一同样绝妙的定理出发,就会突然发现,离停机问题和神奇的Y combinator只是咫尺之遥而已。当然,最后我们会回溯到一切的尽头,康托尔那里,看看停机问题、Y combinator、以及不完备性定理是如何自然而然地由康托尔的对角线方法推导出来的,我们将会看到这些看似神奇的构造性证明的背后,其实是一个简洁优美的数学方法在起作用。
Y Combinator
了解Y combinator的请直接跳过这一节,到下一节哥德尔的不完备性定理
让我们暂且搁下但记住绕人的图灵停机问题,走进函数式编程语言的世界,走进由跟图灵机理论等价的lambda算子发展出来的另一个平行的语言世界。让我们来看一看被人们一代一代吟唱着的神奇的Y Combinator…
关于Y Combinator的文章可谓数不胜数,这个由师从希尔伯特的著名逻辑学家Haskell B.Curry(Haskell语言就是以他命名的,而函数式编程语言里面的Curry手法也是以他命名)“发明”出来的组合算子(Haskell是研究组合逻辑(combinatory logic)的)仿佛有种神奇的魔力,它能够算出给定lambda表达式(函数)的不动点。从而使得递归成为可能。事实上,我们待会就会看到,Y Combinator在神奇的表面之下,其实隐藏着深刻的意义,其背后体现的意义,曾经开出过历史上最灿烂的数学之花,所以MIT的计算机科学系将它做成系徽也就不足为奇了[5]
当然,要了解这个神奇的算子,我们需要一点点lambda算子理论的基础知识,不过别担心,lambda算子理论是我目前见过的最简洁的公理系统,这个系统仅仅由三条非常简单的公理构成,而这三条公理里面我们又只需要关注前两条。
以下小节——lambda calculus——纯粹是为了没有接触过lambda算子理论的读者准备的,并不属于本文重点讨论的东西,然而要讨论Y combinator就必须先了解一下lambda(当然,以编程语言来了解也行,但是你会看到,丘齐最初提出的lambda算子理论才是最最简洁和漂亮的,学起来也最省事。)所以我单独准备了一个小节来介绍它。如果你已经知道,可以跳过这一小节。不知道的读者也可以跳过这一小节去wikipedia上面看,这里的介绍使用了wikipedia上的方式
lambda calculus
先来看一下lambda表达式的基本语法(BNF):
<expr> ::= <identifier>
<expr> ::= lambda <identifier-list>. <expr>
<expr> ::= (<expr> <expr>)
前两条语法用于生成lambda表达式(lambda函数),如:
lambda x y. x + y
haskell里面为了简洁起见用“/”来代替希腊字母lambda,它们形状比较相似。故而上面的定义也可以写成:
/ x y. x + y
这是一个匿名的加法函数,它接受两个参数,返回两值相加的结果。当然,这里我们为了方便起见赋予了lambda函数直观的计算意义,而实际上lambda calculus里面一切都只不过是文本替换,有点像C语言的宏。并且这里的“+”我们假设已经是一个具有原子语义的运算符[6],此外,为了方便我们使用了中缀表达(按照lambda calculus系统的语法实际上应该写成“(+ x y)”才对——参考第三条语法)。
那么,函数定义出来了,怎么使用呢?最后一条规则就是用来调用一个lambda函数的:
((lambda x y. x + y) 2 3)
以上这一行就是把刚才定义的加法函数运用到2和3上(这个调用语法形式跟命令式语言(imperative language)惯用的调用形式有点区别,后者是“f(x, y)”,而这里是“(f x y)”,不过好在顺序没变:) )。为了表达简洁一点,我们可以给(lambda x y. x + y)起一个名字,像这样:
let Add = (lambda x y. x + y)
这样我们便可以使用Add来表示该lambda函数了:
(Add 2 3)
不过还是为了方便起见,后面调用的时候一般用“Add(2, 3)”,即我们熟悉的形式。
有了语法规则之后,我们便可以看一看这个语言系统的两条简单至极的公理了:
Alpha转换公理:例如,“lambda x y. x + y”转换为“lambda a b. a + b”。换句话说,函数的参数起什么名字没有关系,可以随意替换,只要函数体里面对参数的使用的地方也同时注意相应替换掉就是了。
Beta转换公理:例如,“(lambda x y. x + y) 2 3”转换为“2 + 3”。这个就更简单了,也就是说,当把一个lambda函数用到参数身上时,只需用实际的参数来替换掉其函数体中的相应变量即可。
就这些。是不是感觉有点太简单了?但事实就是如此,lambda算子系统从根本上其实就这些东西,然而你却能够从这几个简单的规则中推演出神奇无比的Y combinator来。我们这就开始!
递归的迷思
敏锐的你可能会发现,就以上这两条公理,我们的lambda语言中无法表示递归函数,为什么呢?假设我们要计算经典的阶乘,递归描述肯定像这样:
f(n):
 if n == 0 return 1
 return n*f(n-1)
当然,上面这个程序是假定n为正整数。这个程序显示了一个特点,f在定义的过程中用到了它自身。那么如何在lambda算子系统中表达这一函数呢?理所当然的想法如下:
lambda n. If_Else n==0 1 n*<self>(n-1)
当然,上面的程序假定了If_Else是一个已经定义好的三元操作符(你可以想象C的“?:”操作符,后面跟的三个参数分别是判断条件、成功后求值的表达式、失败后求值的表达式。那么很显然,这个定义里面有一个地方没法解决,那就是<self>那个地方我们应该填入什么呢?很显然,熟悉C这类命令式语言的人都知道应该填入这个函数本身的名字,然而lambda算子系统里面的lambda表达式(或称函数)是没有名字的。
怎么办?难道就没有办法实现递归了?或者说,丘齐做出的这个lambda算子系统里面根本没法实现递归从而在计算能力上面有重大的缺陷?显然不是。马上你就会看到Y combinator是如何把一个看上去非递归的lambda表达式像变魔术那样变成一个递归版本的。在成功之前我们再失败一次,注意下面的尝试:
let F = lambda n. IF_Else n==0 1 n*F(n-1)
看上去不错,是吗?可惜还是不行。因为let F只是起到一个语法糖的作用,在它所代表的lambda表达式还没有完全定义出来之前你是不可以使用F这个名字的。更何况实际上丘齐当初的lambda算子系统里面也并没有这个语法元素,这只是刚才为了简化代码而引入的语法糖。当然,了解这个let语句还是有意义的,后面还会用到。
一次成功的尝试
在上面几次失败的尝试之后,我们是不是就一筹莫展了呢?别忘了软件工程里面的一条黄金定律:“任何问题都可以通过增加一个间接层来解决”。不妨把它沿用到我们面临的递归问题上:没错,我们的确没办法在一个lambda函数的定义里面直接(按名字)来调用其自身。但是,可不可以间接调用呢?
我们回顾一下刚才不成功的定义:
lambda n. If_Else n==0 1 n*<self>(n-1)
现在<self>处不是缺少“这个函数自身”嘛,既然不能直接填入“这个函数自身”,我们可以增加一个参数,也就是说,把<self>参数化:
lambda self n. If_Else n==0 1 n*self(n-1)
上面这个lambda算子总是合法定义了吧。现在,我们调用这个函数的时候,只要加传一个参数self,这个参数不是别人,正是这个函数自身。还是为了简单起见,我们用let语句来给上面这个函数起个别名:
let P = lambda self n. If_Else n==0 1 n*self(n-1)
我们这样调用,比如说我们要计算3的阶乘:
P(P, 3)
也就是说,把P自己作为P的第一个参数(注意,调用的时候P已经定义完毕了,所以我们当然可以使用它的名字了)。这样一来,P里面的self处不就等于是P本身了吗?自身调用自身,递归!
可惜这只是个美好的设想,还差一点点。我们分析一下P(P, 3)这个调用。利用前面讲的Beta转换规则,这个函数调用展开其实就是(你可以完全把P当成一个宏来进行展开!):
IF_Else n==0 1 n*P(n-1)
看出问题了吗?这里的P(n-1)虽然调用到了P,然而只给出了一个参数;而从P的定义来看,它是需要两个参数的(分别为self和n)!也就是说,为了让P(n-1)变成良好的调用,我们得加一个参数才行,所以我们得稍微修改一下P的定义:
let P = lambda self n. If_Else n==0 1 n*self(self, n-1)
请注意,我们在P的函数体内调用self的时候增加了一个参数。现在当我们调用P(P, 3)的时候,展开就变成了:
IF_Else 3==0 1 3*P(P, 3-1)
P(P, 3-1)是对P合法的递归调用。这次我们真的成功了!
不动点原理
然而,看看我们的P的定义,是不是很丑陋?“n*self(self, n-1)”?什么玩意?为什么要多出一个多余的self?DRY!怎么办呢?我们想起我们一开始定义的那个失败的P,虽然行不通,但最初的努力往往是大脑最先想到的最直观的做法,我们来回顾一下:
let P = lambda self n. If_Else n==0 1 n*self(n-1)
这个P的函数体就非常清晰,没有冗余成分,虽然参数列表里面多出一个self,但我们其实根本不用管它,看函数体就行了,self这个名字已经可以说明一切了对不对?但很可惜这个函数不能用。我们再来回想一下为什么不能用呢?因为当你调用P(P, n)的时候,里面的self(n-1)会展开为P(n-1)而P是需要两个参数的。唉,要是这里的self是一个“真正”的,只需要一个参数的递归阶乘函数,那该多好啊。为什么不呢?干脆我们假设出一个“真正”的递归阶乘函数:
power(n):
 if(n==0) return 1;
 return n*power(n-1);
但是,前面不是说过了,这个理想的版本无法在lambda算子系统中定义出来吗(由于lambda函数都是没名字的,无法自己内部调用自己)?不急,我们并不需要它被定义出来,我们只需要在头脑中“假设”它以“某种”方式被定义出来了,现在我们把这个真正完美的power传给P,这样:
P(power, 3)
注意它跟P(P, 3)的不同,P(P, 3)我们传递的是一个有缺陷的P为参数。而P(power, 3)我们则是传递的一个真正的递归函数power。我们试着展开P(power, 3):
IF_Else 3==0 1 3*power(3-1)
发生了什么??power(3-1)将会计算出2的阶乘(别忘了,power是我们设想的完美递归函数),所以这个式子将会忠实地计算出3的阶乘!
回想一下我们是怎么完成这项任务的:我们设想了一个以某种方式构造出来的完美的能够内部自己调用自己的递归阶乘函数power,我们发现把这个power传给P的话,P(power, n)的展开式就是真正的递归计算n阶乘的代码了。
你可能要说:废话!都有了power了我们还要费那事把它传给P来个P(power, n)干嘛?直接power(n)不就得了?! 别急,之所以设想出这个power只是为了引入不动点的概念,而不动点的概念将会带领我们发现Y combinator。
什么是不动点?一点都不神秘。让我们考虑刚才的power与P之间的关系。一个是真正可递归的函数,一个呢,则是以一个额外的self参数来试图实现递归的伪递归函数,我们已经看到了把power交给P为参数发生了什么,对吧?不,似乎还没有,我们只是看到了,“把power加上一个n一起交给P为参数”能够实现真正的递归。现在我们想考虑power跟P之间的关系,直接把power交给P如何?
P(power)
这是什么?这叫函数的部分求值(partial evaluation)。换句话说,第一个参数是给出来了,但第二个参数还悬在那里,等待给出。那么,光给一个参数得到的是什么呢?是“还剩一个参数待给的一个新的函数”。其实也很简单,只要按照Beta转换规则做就是了,把P的函数体里面的self出现处皆替换为power就可以了。我们得到:
IF_Else n==0 1 n*power(n-1)
当然,这个式子里面还有一个变量没有绑定,那就是n,所以这个式子还不能求值,你需要给它一个n才能具体求值,对吧。这么说,这可不就是一个以n为参数的函数么?实际上就是的。在lambda算子系统里面,如果给一个lambda函数的参数不足,则得到的就是一个新的lambda函数,这个新的lambda函数所接受的参数也就是你尚未给出的那些参数。换句话来说,调用一个lambda函数可以分若干步来进行,每次只给出一部分参数,而只有等所有参数都给齐了,函数的求值结果才能出来,否则你得到的就是一个“中间函数”。
那么,这跟不动点定理有什么关系?关系大了,刚才不是说了,P(power)返回的是一个新的“中间函数”嘛?这个“中间函数”的函数体我们刚才已经看到了,就是简单地展开P(power)而已,回顾一遍:
IF_Else n==0 1 n*power(n-1)
我们已经知道,这是个函数,参数n待定。因此我们不妨给它加上一个“lambda n”的帽子,这样好看一点:
lambda n. IF_Else n==0 1 n*power(n-1)
这是什么呢?这可不就是power本身的定义?(当然,如果我们能够定义power的话)。不信我们看看power如果能够定义出来像什么样子:
let power = lambda n. IF_Else n==0 1 n*power(n-1)
一模一样!也就是说,P(power)展开后跟power是一样的。即:
P(power) = power
以上就是所谓的不动点。即对于函数P来说power是这样一个“点”:当把P用到power身上的时候,得到的结果仍然还是power,也就是说,power这个“点”在P的作用下是“不动”的。
可惜的是,这一切居然都是建立在一个不存在的power的基础上的,又有什么用呢?可别过早提“不存在”这个词,你觉得一样东西不存在或许只是你没有找到使它存在的正确方法。我们已经看到power是跟P有着密切联系的。密切到什么程度呢?对于伪递归的P,存在一个power,满足P(power)=power。注意,这里所说的“伪递归”的P,是指这样的形式:
let P = lambda self n. If_Else n==0 1 n*self(n-1) // 注意,不是self(self,n-1)
一般化的描述就是,对任一伪递归F(回想一下伪递归的F如何得到——是我们为了解决lambda函数不能引用自身的问题,于是给理想的f加一个self参数从而得到的),必存在一个理想f(F就是从这个理想f演变而来的),满足F(f) = f。
那么,现在的问题就归结为如何针对F找到它的f了。根据F和f之间的密切联系(F就比f多出一个self参数而已),我们可以从F得出f吗?假设我们可以(又是假设),也就是说假设我们找到了一根魔棒,把它朝任意一个伪递归的F一挥,眼前一花,它就变成了真正的f了。这根魔棒如果存在的话,它具有什么性质?我们假设这个神奇的函数叫做Y,把Y用到任何伪递归的函数F上就能够得到真正的f,也就是说:
Y(F) = f
结合上面的F(f) = f,我们得到:
Y(F) = f = F(f) = F(Y(F))
也就是说,Y具有性质:
Y(F) = F(Y(F))
性质倒是找出来了,怎么构造出这个Y却又成了难题。一个办法就是使用抽象法,这是从工程学的思想的角度,也就是通过不断迭代、重构,最终找到问题的解。然而对于这里的Y combinator,接近问题解的过程却显得复杂而费力,甚至过程中的有些点上的思维跳跃有点如羚羊挂角无迹可寻。然而,在这整个Y combinator介绍完了之后我们将会介绍著名的哥德尔不完备性定理,然后我们就会发现,通过哥德尔不完备性定理证明中的一个核心构造式,只需一步自然的推导就能得出我们的Y combinator。而且,最美妙的是,还可以再往下归约,把一切都归约到康托尔当初提出的对角线方法,到那时我们就会发现原来同样如羚羊挂角般的哥德尔的证明其实是对角线方法的一个自然推论。数学竟是如此奇妙,我们由简单得无法再简单的lambda calculus系统的两条公理居然能够导出如此复杂如此令人目眩神迷的Y Combinator,而这些复杂性其实也只是荡漾在定理海洋中的涟漪,拨开复杂性的迷雾我们重又发现它们居然寓于极度的简洁之中。这就是数学之美。
让我们先来看一看Y combinator的费力而复杂的工程学构造法,我会尽量让这个过程显得自然而流畅[7]
我们再次回顾一下那个伪递归的求阶乘函数:
let P = lambda self n. If_Else n==0 1 n*self(n-1)
我们的目标是找出P的不动点power,根据不动点的性质,只要把power传给P,即P(power),便能够得到真正的递归函数了。
现在,关键的地方到了,由于:
power = P(power) // 不动点原理
这就意味着,power作为一个函数(lambda calculus里面一切都是函数),它是自己调用了自己的。那么,我们如何实现这样一个能够自己调用自己的power呢?回顾我们当初成功的一次尝试,要实现递归,我们是通过增加一个间接层来进行的:
let power_gen = lambda self. P(self(self))
还记得self(self)这个形式吗?我们在成功实现出求阶乘递归函数的时候不就是这么做的?那么对于现在这个power_gen,怎么递归调用?
power_gen(power_gen)
不明白的话可以回顾一下前面我们调用P(P, n)的地方。这里power_gen(power_gen)展开后得到的是什么呢?我们根据刚才power_gen的定义展开看一看,原来是:
P(power_gen(power_gen))
看到了吗?也就是说:
power_gen(power_gen) => P(power_gen(power_gen))
 
现在,我们把power_gen(power_gen)当成整体看,不妨令为power,就看得更清楚了:
power => P(power)
这不正是我们要的答案么?
OK,我们总结一下:对于给定的P,只要构造出一个相应的power_gen如下:
let power_gen = lambda self. P(self(self))
我们就会发现,power_gen(power_gen)这个调用展开后正是P(power_gen(power_gen))。也就是说,我们的power_gen(power_gen)就是我们苦苦寻找的不动点了!
铸造Y Combinator
现在我们终于可以铸造我们的Y Combinator了,Y Combinator只要生成一个形如power_gen的lambda函数然后把它应用到自身,就大功告成:
let Y = lambda F.
let f_gen = lambda self. F(self(self))
return f_gen(f_gen)
稍微解释一下,Y是一个lambda函数,它接受一个伪递归F,在内部生成一个f_gen(还记得我们刚才看到的power_gen吧),然后把f_gen应用到它自身(记得power_gen(power_gen)吧),得到的这个f_gen(f_gen)也就是F的不动点了(因为f_gen(f_gen) = F(f_gen(f_gen))),而根据不动点的性质,F的不动点也就是那个对应于F的真正的递归函数!
如果你还觉得不相信,我们稍微展开一下看看,还是拿阶乘函数说事,首先我们定义阶乘函数的伪递归版本:
let Pwr = lambda self n. If_Else n==0 1 n*self(n-1)
让我们把这个Pwr交给Y,看会发生什么(根据刚才Y的定义展开吧):
Y(Pwr) =>
 let f_gen = lambda self. Pwr(self(self))
 return f_gen(f_gen)
Y(Pwr)的求值结果就是里面返回的那个f_gen(f_gen),我们再根据f_gen的定义展开f_gen(f_gen),得到:
Pwr(f_gen(f_gen))
也就是说:
Y(Pwr) => f_gen(f_gen) => Pwr(f_gen(f_gen))
我们来看看得到的这个Pwr(f_gen(f_gen))到底是不是真有递归的魔力。我们展开它(注意,因为Pwr需要两个参数,而我们这里只给出了一个,所以Pwr(f_gen(f_gen))得到的是一个单参(即n)的函数):
Pwr(f_gen(f_gen)) => If_Else n==0 1 n*f_gen(f_gen) (n-1)
而里面的那个f_gen(f_gen),根据f_gen的定义,又会展开为Pwr(f_gen(f_gen)),所以:
Pwr(f_gen(f_gen)) => If_Else n==0 1 n* Pwr(f_gen(f_gen)) (n-1)
看到加粗的部分了吗?因为Pwr(f_gen(f_gen))是一个接受n为参数的函数,所以不妨把它令成f(f的参数是n),这样上面的式子就是:
f => If_Else n==0 1 n*f(n-1)
完美的阶乘函数!
哥德尔的不完备性定理
了解哥德尔不完备性定理的可以跳到下一节,大道至简——康托尔的天才
然而,漫长的Y Combinator征途仍然并非本文的最终目的,对于Y combinator的构造和解释,只是给不了解lambda calculus或Y combinator的读者看的。关键是马上你会看到Y combinator可以由哥德尔不完备性定理证明的一个核心构造式一眼瞧出来!
让我们的思绪回到1931年,那个数学界风起云涌的年代,一个名不经传的20出头的学生,在他的博士论文中证明了一个惊天动地的结论。
在那个年代,希尔伯特的数学天才就像太阳的光芒一般夺目,在关于数学严格化的大纷争中希尔伯特带领的形式主义派系技压群雄,得到许多当时有名望的数学家的支持。希尔伯特希望借助于形式化的手段,抽掉数学证明中的意义,把数学证明抽象成一堆无意义的符号转换,就连我们人类赖以自豪的逻辑推导,也不过只是一堆堆符号转换而已(想起lambda calculus系统了吧:))。这样一来,一个我们日常所谓的,带有直观意义和解释的数学系统就变成了一个纯粹由无意义符号表达的、公理加上推导规则所构成的形式系统,而数学证明呢,只不过是在这个系统内玩的一个文字游戏。令人惊讶的是,这样一种做法,真的是可行的!数学的意义,似乎竟然真的可以被抽掉!另一方面,一个形式系统具有非常好的性质,平时人们证明一个定理所动用的推导,变成了纯粹机械的符号变换。希尔伯特希望能够证明,在任一个无矛盾的形式系统中所能表达的所有陈述都要么能够证明要么能够证伪。这看起来是个非常直观的结论,因为一个结论要么是真要么是假,而它在它所处的领域/系统中当然应该能够证明或证伪了(只要我们能够揭示出该系统中足够多的真理)。
然而,哥德尔的证明无情的击碎了这一企图,哥德尔的证明揭示出,任何足够强到蕴含了皮亚诺算术系统(PA)的一致(即无矛盾)的系统都是不完备的,所谓不完备也就是说在系统内存在一个为真但无法在系统内推导出的命题。这在当时的数学界揭起了轩然大波,其证明不仅具有数学意义,而且蕴含了深刻的哲学意义。从那时起这一不完备性定理就被引申到自然科学乃至人文科学的各个角落…至今还没有任何一个数学定理居然能够产生这么广泛而深远的影响。
哥德尔的证明非常的长,达到了200多页纸,但其中很大的成分是用在了一些辅助性的工作上面,比如占据超过1/3纸张的是关于一个形式系统如何映射到自然数,也就是说,如何把一个形式系统中的所有公式都表示为自然数,并可以从一自然数反过来得出相应的公式。这其实就是编码,在我们现在看来是很显然的,因为一个程序就可以被编码成二进制数,反过来也可以解码。但是在当时这是一个全新的思想,也是最关键的辅助性工作之一,另一方面,这正是“程序即数据”的最初想法。
现在我们知道,要证明哥德尔的不完备性定理,只需在假定的形式系统T内表达出一个为真但无法在T内推导出(证明)的命题。于是哥德尔构造了这样一个命题,用自然语言表达就是:命题P说的是“P不可在系统T内证明”(这里的系统T当然就是我们的命题P所处的形式系统了),也就是说“我不可以被证明”,跟著名的说谎者悖论非常相似,只是把“说谎”改成了“不可以被证明”。我们注意到,一旦这个命题能够在T内表达出来,我们就可以得出“P为真但无法在T内推导出来”的结论,从而证明T的不完备性。为什么呢?我们假设T可以证明出P,而因为P说的就是P不可在系统T内证明,于是我们又得到T无法证明出P,矛盾产生,说明我们的假设“T可以证明P”是错误的,根据排中律,我们得到T不可以证明P,而由于P说的正是“T不可证明P”,所以P就成了一个正确的命题,同时无法由T内证明!
如果你足够敏锐,你会发现上面这番推理本身不就是证明吗?其证明的结果不就是P是正确的?然而实际上这番证明是位于T系统之外的,它用到了一个关于T系统的假设“T是一致(无矛盾)的”,这个假设并非T系统里面的内容,所以我们刚才其实是在T系统之外推导出了P是正确的,这跟P不能在T推导出来并不矛盾。所以别担心,一切都正常。
那么,剩下来最关键的问题就是如何用形式语言在T内表达出这个P,上面的理论虽然漂亮,但若是P根本没法在T内表达出来,我们又如何能证明“T内存在这个为真但无法被证明的P”呢?那一切还不是白搭?
于是,就有了哥德尔证明里面最核心的构造,哥德尔构造了这样一个公式:
N(n) is unprovable in T
这个公式由两部分构成,n是这个公式的自由变量,它是一个自然数,一旦给定,那么这个公式就变成一个明确的命题。而N则是从n解码出的货真价实的(即我们常见的符号形式的)公式(记得哥德尔的证明第一部分就是把公式编码吗?)。”is unprovable in T”则是一个谓词,这里我们没有用形式语言而是用自然语言表达出来的,但哥德尔证明了它是可以用形式语言表达出来的,大致思路就是:一个形式系统中的符号数目是有限的,它们构成这个形式系统的符号表。于是,我们可以依次枚举出所有长度为1的串,长度为2的串,长度为3的串… 此外根据形式系统给出的语法规则,我们可以检查每个串是否是良构的公式(well formed formula,简称wff,其实也就是说,是否符合语法规则,前面我们在介绍lambda calculus的时候看到了,一个形式系统是需要语法规则的,比如逻辑语言形式化之后我们就会看到P->Q是一个wff,而->PQ则不是),因而我们就可以枚举出所有的wff来。最关键的是,我们观察到形式系统中的证明也不过就是由一个个的wff构成的序列(想想推导的过程,不就是一个公式接一个公式嘛)。而wff构成的序列本身同样也是由符号表内的符号构成的串。所以我们只需枚举所有的串,对每一个串检查它是否是一个由wff构成的序列(证明),如果是,则记录下这个wff序列(证明)的最后一个wff,也就是它的结论。这样我们便枚举出了所有的可由T推导出的定理。然后为了表达出”X is unprovable in T”,本质上我们只需说“不存在这样一个自然数S,它所解码出来的wff序列以X为终结”!这也就是说,我们表达出了“is unprovable in T”这个谓词。
我们用UnPr(X)来表达“X is unprovable in T”,于是哥德尔的公式变成了:
UnPr( N(n) )
现在,到了最关键的部分,首先我们把这个公式简记为G(n)——别忘了G内有一个自由变量n,所以G现在还不是一个命题,而只是一个公式,所以谈不上真假:
G(n): UnPr( N(n) )
又由于G也是个wff,所以它也有自己的编码g,当然g是一个自然数,现在我们把g作为G的参数,也就是说,把G里面的自由变量n替换为g,我们于是得到一个真正的命题:
G(g): UnPr( G(g) )
用自然语言来说,这个命题G(g)说的就是“我是不可在T内证明的”。看,我们在形式系统T内表达出了“我是不可在T内证明的”这个命题。而我们一开始已经讲过了如何用这个命题来推断出G(g)为真但无法在T内证明,于是这就证明了哥德尔的不完备性定理[8]
哥德尔的不完备性定理被称为20世纪数学最重大的发现(不知道有没有“之一”:) )现在我们知道为真但无法在系统内证明的命题不仅仅是这个诡异的“哥德尔命题”,还有很多真正有意义的明确命题,其中最著名的就是连续统假设,此外哥德巴赫猜想也有可能是个没法在数论系统中证明的真命题。
从哥德尔公式到Y Combinator
哥德尔的不完备性定理证明了数学是一个未完结的学科,永远有需要我们以人的头脑从系统之外去用我们独有的直觉发现的东西。罗杰·彭罗斯在《The Emperor’s New Mind》中用它来证明人工智能的不可实现。当然,这个结论是很受质疑的。但哥德尔的不完备性定理的确还有很多很多的有趣推论,数学的和哲学上的。哥德尔的不完备性定理最深刻的地方就是它揭示了自指(或称自引用,递归调用自身等等)结构的普遍存在性,我们再来看一看哥德尔命题的绝妙构造:
G(n): UnPr( N(n) )
我们注意到,这里的UnPr其实是一个形式化的谓词,它不一定要说“X在T内可证明”,我们可以把它泛化为一个一般化的谓词,P:
G(n): P( N(n) )
也就是说,对于任意一个单参的谓词P,都存在上面这个哥德尔公式。然后我们算出这个哥德尔公式的自然数编码g,然后把它扔给G,就得到:
G(g): P( G(g) )
是不是很熟悉这个结构?我们的Y Combinator的构造不就是这样一个形式?我们把G和P都看成一元函数,G(g)可不正是P这个函数的不动点么!于是,我们从哥德尔的证明里面直接看到了Y Combinator
至于如何从哥德尔的证明联系到停机问题,就留给你去解决吧:) 因为更重要的还在后面,我们看到,哥德尔的证明虽然巧妙至极,然而其背后的思维过程仍然飘逸而不可捉摸,至少我当时看到G(n)的时候,“乃大惊”“不知所从出”,他怎么想到的?难道是某一个瞬间“灵光一现”?一般我是不信这一说的,已经有越来越多的科学研究表明一瞬间的“灵感”往往是潜意识乃至表层意识长期思考的结果。哥德尔天才的证明也不例外,我们马上就会看到,在这个神秘的构造背后,其实隐藏着某种更深的东西,这就是康托尔在19世纪80年代研究无穷集合和超限数时引入的对角线方法。这个方法仿佛有种神奇的力量,能够揭示出某种自指的结构来,而同时,这又是一个极度简单的手法,通过它我们能够得到数学里面一些非常奇妙的性质。无论是哥德尔的不完备性定理还是再后来丘齐建立的lambda calculus,抑或我们非常熟悉的图灵机理论里的停机问题,其实都只是这个手法简单推演的结果!
大道至简——康托尔的天才
“大道至简”这个名词或许更多出现在文学和哲学里面,一般用在一些模模糊糊玄玄乎乎的哲学观点上。然而,用在这里,数学上,这个名词才终于适得其所。大道至简,看上去最复杂的理论其实建立在一个最简单最纯粹的道理之上。
康托尔在无穷集合和超限数方面的工作主要集中在两篇突破性的论文上,这也是我所见过的最纯粹最美妙的数学论文,现代的数学理论充斥了太多复杂的符号和概念,很多时候让人看不到最本质的东西,当然,不否认这些东西很多也是有用的,然而,要领悟真正的数学美,像集合论和数论这种纯粹的东西,真的非常适合。不过这里就不过多谈论数学的细节了,只说康托尔引入对角线方法的动机和什么是对角线方法。
神奇的一一对应
康托尔在研究无穷集合的时候,富有洞察性地看到了对于无穷集合的大小问题,我们不能再使用直观的“所含元素的个数”来描述,于是他创造性地将一一对应引入进来,两个无穷集合“大小”一样当且仅当它们的元素之间能够构成一一对应。这是一个非常直观的概念,一一对应嘛,当然个数相等了,是不是呢?然而这同时就是它不直观的地方了。对于无穷集合,我们日常的所谓“个数”的概念不管用了,因为无穷集合里面的元素个数本就是无穷多个。不信我们来看一个小小的例子。我们说自然数集合能够跟偶数集合构成一一对应,从而自然数集合跟偶数集合里面元素个数是一样多的。怎么可能?偶数集合是自然数集合的真子集,所有偶数都是自然数,但自然数里面还包含奇数呢,说起来应该是二倍的关系不是?不是!我们只要这样来构造一一对应:
1 2 3 4 …
2 4 6 8 …
用函数来描述就是 f(n) = 2n。检验一下是不是一一对应的?不可思议对吗?还有更不可思议的,自然数集是跟有理数集一一对应的!对应函数的构造就留给你解决吧,提示,按如下方式来挨个数所有的有理数:
1/1  1/2  2/1  1/3  2/2  3/1  1/4  2/3 3/2 4/1 …
用这种一一对应的手法还可以得到很多惊人的结论,如一条直线上所有的点跟一个平面上所有的点构成一一对应(也就是说复数集合跟实数集合构成一一对应)。以致于连康托尔自己都不敢相信自己的眼睛了,这也就是为什么他在给戴得金的信中会说“我看到了它,却不敢相信它”的原因。
然而,除了一一对应之外,还有没有不能构成一一对应的两个无穷集合呢?有。实数集合就比自然数集合要,它们之间实际上无法构成一一对应。这就是康托尔的对角线方法要解决的问题。
实数集和自然数集无法构成一一对应?!
我们只需将实数的小数位展开,并且我们假设实数集能够与自然数集一一对应,也就是说假设实数集可列,所以我们把它们与自然数一一对应列出,如下:
1  a10.a11a12a13
2  a20.a21a22a23
3  a30.a31a32a33
4 …
5 …
(注:aij里面的ij是下标)
现在,我们构造一个新的实数,它的第i位小数不等于aii。也就是说,它跟上面列出的每一个实数都至少有一个对应的小数位不等,也就是说它不等于我们上面列出的所有实数,这跟我们上面假设已经列出了所有实数的说法相矛盾。所以实数集只能是不可列的,即不可与自然数集一一对应!这是对角线方法的最简单应用。
对角线方法——停机问题的深刻含义
对角线方法有很多非常奇妙的结论。其中之一就是文章一开始提到的停机问题。我想绝大多数人刚接触停机问题的时候都有一个问题,图灵怎么能够想到这么诡异的证明,怎么能构造出那个诡异的“说停机又不停机,说不停机又停机”的悖论机器。马上我们就会看到,这其实只是对角线方法的一个直接结论。
还是从反证开始,我们假设存在这样一个图灵机,他能够判断任何程序在任何输入上是否停机。由于所有图灵机构成的集合是一个可列集(也就是说,我们可以逐一列出所有的图灵机,严格证明见我以前的一篇文章《图灵机杂思》),所以我们可以很自然地列出下表,它表示每个图灵机分别在每一个可能的输入(1,2,3,…)下的输出,N表示无法停机,其余数值则表示停机后的输出:
     1    2     3    4   …
M1  N    1    N    N   …
M2  2    0     N    0   …
M3  0    1     2    0    …
M4  N    0     5    N   …
M1,M2,M3 … 是逐一列出的图灵机,并且,注意,由于程序即数据,每个图灵机都有唯一编码,所以我们规定在枚举图灵机的时候Mi其实就代表编码为i的图灵机,当然这里很多图灵机将会是根本没用的玩意,但这不要紧。此外,最上面的一行1 2 3 4 … 是输入数据,如,矩阵的第一行代表M1分别在1,2,3,…上面的输出,不停机的话就是N。
我们刚才假设存在这样一个图灵机H,它能够判断任何程序在任何输入上能否停机,换句话说,H(i,j)(i是Mi的编码)能够给出“Mi(j)”是N(不停)呢还是给出一个具体的结果(停)。
我们现在来运用康托尔的对角线方法,我们构造一个新的图灵机P,P在1上的输出行为跟M1(1)“不一样”,在2上的输出行为跟M2(2)“不一样”,…总之P在输入i上的输出跟Mi(i)不一样。只需利用一下我们万能的H,这个图灵机P就不难构造出来,如下:
P(i):
if( H(i, i) == 1 ) then // Mi(i) halts
return 1 + Mi(i)
else // if H(i, i) == 0 (Mi(i) doesn’t halt)
    return 0
也就是说,如果Mi(i)停机,那么P(i)的输出就是Mi(i)+1,如果Mi(i)不停机的话,P(i)就停机且输出0。这就保证了P(i)的输出行为跟Mi(i)反正不一样。现在,我们注意到P本身是一个图灵机,而我们上面已经列出了所有的图灵机,所以必然存在一个k,使得Mk = P。而两个图灵机相等当且仅当它们对于所有的输入都相等,也就是说对于任取的n,有Mk(n) = P(n),现在令n=k,得到Mk(k)=P(k),根据上面给出的P的定义,这实际上就是:
Mk(k) = P(k) =
1+Mk(k) if Mk(k) halts
0       if Mk(k) doesn’t halt
看到这个式子里蕴含的矛盾了吗?如果Mk(k)停机,那么Mk(k)=1+Mk(k);如果Mk(k)不停机,则Mk(k)=0(给出结果0即意味着Mk(k)停机);不管哪种情况都是矛盾。于是我们得出,不存在那样的H。
这个对角线方法实际上说明了,无论多聪明的H,总存在一个图灵机的停机行为是它无法判断的。这跟哥德尔定理“无论多‘完备’的形式化公理系统,都存在一个‘哥德尔命题’是无法在系统内推导出来的”从本质上其实是一模一样的。只不过我们一般把图灵的停机问题称为“可判定问题”,而把数学的称为“可证明问题”。
等等!如果我们把那个无法判定是否停机的图灵机作为算法的特例纳入到我们的H当中呢?我们把得到的新的判定算法记为H1。然而,可惜的是,在H1下,我们又可以相应地以同样的手法从H1构造出一个无法被它(H1)判定的图灵机来。你再加,我再构造,无论你加多少个特例进去,我都可以由同样的方式构造出来一个你无法够到的图灵机,以彼之矛,攻彼之盾。其实这也是哥德尔定理最深刻的结论之一,哥德尔定理其实就说明了无论你给出多少个公理,即无论你建立多么完备的公理体系,这个系统里面都有由你的那些公理出发所推导不到的地方,这些黑暗的角落,就是人类直觉之光才能照射到的地方!
本节我们从对角线方法证明了图灵的停机问题,我们看到,对角线方法能够揭示出某种自指结构,从而构造出一个“悖论图灵机”。实际上,对角线方法是一种有深远影响的方法,哥德尔的证明其实也是这个方法的一则应用。证明与上面的停机问题证明如出一辙,只不过把Mi换成了一个形式系统内的公式fi,具体的证明就留给聪明的你吧:)我们现在来简单的看一下这个奇妙方法的几个不那么明显的推论。
罗素悖论
学过逻辑的人大约肯定是知道著名的罗素悖论的,罗素悖论用数学的形式来描述就是:
R = {X:X不属于X};
这个悖论最初是从康托尔的无穷集合论里面引申出来的。当初康托尔在思考无穷集合的时候发现可以称“一切集合的集合”,这样一个集合由于它本身也是一个集合,所以它就属于它自身。也就是说,我们现在可以称世界上存在一类属于自己的集合,除此之外当然就是不属于自己的集合了。而我们把所有不属于自己的集合收集起来做成一个集合R,这就是上面这个著名的罗素悖论了。
我们来看R是否属于R,如果R属于R,根据R的定义,R就不应该属于R。而如果R不属于R,则再次根据R的定义,R就应该属于R。
这个悖论促使了集合论的公理化。后来策梅罗公理化的集合论里面就不允许X属于X(不过可惜的是,尽管如此还是没法证明这样的集合论不可能产生出新的悖论。而且永远没法证明——这就是哥德尔第二不完备性定理的结论——一个包含了PA的形式化公理系统永远无法在内部证明其自身的一致(无矛盾)性。从而希尔伯特想从元数学推出所有数学系统的一致性的企图也就失败了,因为元数学的一致性又得由元元数学来证明,后者的一致性又得由元元元数学来证明…)。
这里我们只关心罗素是如何想出这个绝妙的悖论的。还是对角线方法!我们罗列出所有的集合,S1,S2,S3 …
    S1  S2  S3 …
S1 0   1  1 …
S2 1   1   0 …
S3 0   0   0 …
…    …
右侧纵向列出所有集合,顶行横向列出所有集合。0/1矩阵的(i,j)处的元素表示Si是否包含Sj,记为Si(j)。现在我们只需构造一个新的0/1序列L,它的第i位与矩阵的(i,i)处的值恰恰相反:L(i) = 1-Si(i)。我们看到,这个新的序列其实对应了一个集合,不妨也记为L,L(i)表示L是否包含Si。根据L的定义,如果矩阵的(i,i)处值为0(也就是说,如果Si不包含Si),那么L这个集合就包含Si,否则就不包含。我们注意到这个新的集合L肯定等于某个Sk(因为我们已经列出了所有的集合),L = Sk。既然L与Sk是同一集合,那么它们肯定包含同样的元素,从而对于任意n,有L(n) = Sk(n)。于是通过令n=k,得到L(k) = Sk(k),而根据L的定义,L(k) = 1- Sk(k)。这就有Sk(k) = 1-Sk(k),矛盾。
通过抽象简化以上过程,我们看到,我们构造的L其实是“包含了所有不包含它自身的集合的集合”,用数学的描述正是罗素悖论!
敏锐的你可能会注意到所有集合的数目是不可数的从而根本不能S1,S2…的一一列举出来。没错,但通过假设它们可以列举出来,我们发现了一个与可列性无关的悖论。所以这里的对角线方法其实可以说是一种启发式方法。
同样的手法也可以用到证明P(A)(A的所有子集构成的集合,也叫幂集)无法跟A构成一一对应上面。证明就留给聪明的你了:)
希尔伯特第十问题结出的硕果
希尔伯特是在1900年巴黎数学家大会上提出著名的希尔伯特第十问题的,简言之就是是否存在一个算法,能够计算任意丢番图方程是否有整根。要解决这个问题,就得先严格定义“算法”这一概念。为此图灵和丘齐分别提出了图灵机和lambda calculus这两个概念,它们从不同的角度抽象出了“有效(机械)计算”的概念,著名的图灵——丘齐命题就是说所有可以有效计算出来的问题都可以由图灵机计算出来。实际上我们已经看到,丘齐的lambda calculus其实就是数学推理系统的一个形式化。而图灵机则是把这个数学概念物理化了。而也正因为图灵机的概念隐含了实际的物理实现,所以冯·诺依曼才据此提出了奠定现代计算机体系结构的冯·诺依曼体系结构,其遵循的,正是图灵机的概念。而“程序即数据”的理念,这个发端于数学家哥德尔的不完备性定理的证明之中的理念,则早就在黑暗中预示了可编程机器的必然问世。
对角线方法——回顾
我们看到了对角线方法是如何简洁而深刻地揭示出自指或递归结构的。我们看到了著名的不完备性定理、停机问题、Y Combinator、罗素悖论等等等等如何通过这一简洁优美的方法推导出来。这一诞生于康托尔的天才的手法如同一条金色的丝线,把位于不同年代的伟大发现串联了起来,并且将一直延续下去…
P.S
1. lambda calculus里面的“停机问题”
实际上lambda calculus里面也是有“停机问题”的等价版本的。其描述就是:不存在一个算法能够判定任意两个lambda函数是否等价。所谓等价当然是对于所有的n,有f(n)=g(n)了。这个问题的证明更加能够体现对角线方法的运用。仍然留给你吧。
2. 负喧琐话(http://blog.csdn.net/g9yuayon)是个非常不错的blog:)。g9的文字轻松幽默,而且有很多名人八卦可以养眼,真的灰常…灰常…不错哦。此外g9老兄还是个理论功底非常扎实的牛。所以,anyway,看了他的blog就知道啦!最初这篇文章的动机也正是看了上面的一篇关于Y Combinator的铸造过程的介绍,于是想揭示一些更深的东西,于是便有了本文。
3. 文章起名《康托尔、哥德尔、图灵——永恒的金色对角线》其实是为了纪念看过的一本好书GEB,即《Godel、Escher、Bach-An Eternal Golden Braid》中文译名《哥德尔、埃舍尔、巴赫——集异璧之大成》——商务印书馆出版。对于一本定价50元居然能够在douban上卖到100元的二手旧书,我想无需多说。另,幸福的是,电子版可以找到:)
4. 其实很久前想写的是一篇《从哥德尔到图灵》,但那篇写到1/3不到就搁下了,一是由于事务,二是总觉得少点什么。呵呵,如今把康托尔扯进来,也算是完成当时扔掉的那一篇吧。
5. 这恐怕算是写得最曲折的一篇文章了。不仅自己被这些问题搞得有点晕头转向(还好总算走出来),更因为要把这些东西自然而然的串起来,也颇费周章。很多时候是利用吃饭睡觉前或走路的时间思考本质的问题以及如何表达等等,然后到纸上一气呵成。不过同时也锻炼了不拿纸笔思考数学的能力,呵呵。
6. 关于图灵的停机问题、Y Combinator、哥德尔的不完备性定理以及其它种种与康托尔的对角线之间的本质联系,几乎查不到完整系统的深入介绍,一些书甚至如《The Emperor’s New Mind》也只是介绍了与图灵停机问题之间的联系(已经非常的难得了),google和baidu的结果也是基本没有头绪。很多地方都是一带而过让人干着急。所以看到很多地方介绍这些定理和构造的时候都是弄得人晕头转向的,绝大部分人在面对如Y Combinator、不完备性定理、停机问题的时候都把注意力放在力图理解它是怎么运作的上面了,却使人看不到其本质上从何而来,于是人们便对这些东东大为惊叹。这使我感到很不痛快,如隔靴搔痒般。这也是写这篇文章的主要动机之一。
Reference
[1] 《数学——确定性的丧失》
[2] 也有观点认为函数式编程语言之所以没有广泛流行起来是因为一些实际的商业因素。
[3] Douglas R.Hofstadter的著作《Godel, Escher, Bach: An Eternal Golden Braid》(《哥德尔、艾舍尔、巴赫——集异璧之大成》)就是围绕这一思想写出的一本奇书。非常建议一读。
[4] 《数学——确定性的丧失》
[5] 虽然我觉得那个系徽做得太复杂,要表达这一简洁优美的思想其实还能有更好的方式。
[6] 关于如何在lambda calculus系统里实现“+”操作符以及自然数等等,可参见这里,这里,和这里。
[7] g9的blog(负暄琐话)http://blog.csdn.net/g9yuayon/ 上有一系列介绍lambda calculus的文章(当然,还有其它好文章:)),非常不错,强烈推荐。最近的两篇就是介绍Y combinator的。其中有一篇以javaScript语言描述了迭代式逐步抽象出Y Combinator的过程。
[8] 实际上这只是第一不完备性定理,它还有一个推论,被称为第二不完备性定理,说的是任一个系统T内无法证明这个系统本身的一致性。这个定理的证明核心思想如下:我们前面证明第一不完备性定理的时候用的推断其实就表明 Con/T -> G(g) (自然语言描述就是,由系统T的无矛盾,可以推出G(g)成立),而这个“Con/T -> G(g)”本身又是可以在T内表达且证明出来的(具体怎么表达就不再多说了)——只需要用排中律即可。于是我们立即得到,T里面无法推出Con/T,因为一旦推出Con/T就立即推出G(g)从而推出UnPr(G(g)),这就矛盾了。所以,Con/T无法在T内推出(证明)。
from:http://blog.csdn.net/pongba/article/details/1336028

ArchSummit北京2014大会(PPT)

1219日幻灯片资料下载(部分)
时间 2014年12月19日
9:30 论高度Web化之影响
Dave Arel
10:30 冯诺依曼等技术先贤留下的API规模经济启示
Mike Amundsen
11:30 大数据的十个技术前沿
英特尔中国研究院 吴甘沙
专题 转型中的 研发体系构建 互联网金融 疯狂双十一的全栈技术路线图 云平台技术全景剖析
13:30 大数据时代的feed流架构 互联网企业制胜利器——选对人、速度快 证券交易系统架构设计挑战与实施经验分享 京东商城交易系统双11总结 云计算架构的实战案例
新浪微博 杨卫华 奇虎360 谭晓生 上交所 陈晨 京东商城 王晓钟 阿里云 黄湘龙(龙觉)
14:30 Nice服务端架构变迁 远距离条件下的康威定律——分布式世界中实现团 站在电商平台上的互联网金融系统架构实践 双11——淘宝的下一代架构的成人礼 阿里云虚拟化技术研发之路
Nice技术合伙人 程㭎 Mike Amundsen 京东 赵海峰 阿里技术保障 梁耀斌 阿里云 张献涛(旭卿)
15:45 移动互联网海量访问系统设计 Tower团队24个月的远程协作实践 互联网金融系统中的资金正确性保障 OceanBase-支付宝交易O2O最佳实践 阿里云CDN技术演进
微信红包 张晋铭 彩程科技 沈学良 维金 陆怡 阿里巴巴 师文汇(虞舜) 阿里云 朱照远(叔度)
16:45 知乎从0到100 技术驱动型公司的精益实践 互联网金融下的智能客户服务探索 从双十一看天猫订单数据对接及订单流程优化 分析数据库ADS的产品化、服务化
知乎 李申申 LeanCloud CTO 丰俊文 蚂蚁金服 阮征 小米科技 杨大伟 阿里巴巴占超群(离哲)
1220日幻灯片资料下载(部分)
时间 2014年12月20日
专题 智能硬件,更懂你 电商,不是搭个平台就能赢 移动互联网,随时随地 云计算与大数据,从技术选型说起 真实的云计算服务
出品人 豌豆机器小组罗未 京东吴博 淘宝庄卓然 小米冯宏华 InfoQ 包研
9:30 开源硬件的智能之芯 重构再重构,当当网架构演进及规划实现 手机QQ的移动网络实践之路 豌豆荚分布式Redis的设计与实现 NoSQL数据库的事务机制实现
北京融汇科艺 肖文鹏 当当网 史海峰 腾讯手Q 范瑞彬 豌豆荚 刘奇 巨杉数据库 王涛
10:30 智能热潮推进家庭数字娱乐变革 Qunar酒店交易系统架构实践 HTML5移动Web:数百万用户的 MiCloud 挑战和架构演进 一个移动互联网数据分析公司的架构实践
小米 李创奇 去哪儿网 莫德友 Dave Arel 小米科技 张弘强/刘绍辉 友盟 叶谦
11:30 无人机的科幻与现实 千万级电商物流系统是怎么练成的— 来自京东青龙系统的最佳实践 去哪儿SPA HTML应用架构——让HTML应用体验更贴近于Native应用 大数据统计分析平台架构故事—TalkingData数据库架构变迁 七牛云存储产品的三年演进之路
极飞CEO 彭斌 京东 李鹏涛 去哪儿网 蔡欢 TalkingData 周海鹏 七牛云存储 韩拓
13:30 互联网企业做智能硬件的那些坑 多IDC部署的电商网站的缓存管理 手机淘宝架构演化实践 京东实时数据平台技术实践 Aurora、Lambda与亚马逊AWS高可用性架构设计最佳实践
暴风影音 毕先春 一号店 张珺 手机淘宝 李敏 京东 刘彦伟 AWS 张荣典
14:30 智能驾驶:过去、现在和未来 天猫“五化”战略下的电商架构 下一代移动云服务架构 大数据应用中数据安全和数据分析 如何在云上构建复杂的企业级应用
中国无人车 张天雷 天猫 何崚(大少) 雅虎 朱凌 英特尔中国研究院 周鑫 青云QingCloud 甘泉
15:45 智能硬件云平台的发展之路与展望 唯品会供应链技术架构的实践 移动音乐服务的竞争力 HBase上搭建广告实时数据处理平台 基于Ceph的UOSCloud 块存储方案
京东 任强 唯品会 梁德伟 虾米 郭彦儒 腾讯 李锐 UnitedStack 王豪迈
16:45 圆桌论坛 从技术细节看美团的架构 猿题库的技术演化 百度集群操作系统Matrix 从漏洞修复看各国网络战防御能力
谁最有可能成为智能硬件的BAT 美团网 夏华夏 猿题库 唐巧 百度 吕毅 知道创宇 杨冀龙

计算的极限系列及图灵机

希尔伯特之梦,以及梦的破灭 http://songshuhui.net/archives/20161
计算的极限(零):逻辑与图灵机 http://songshuhui.net/archives/70194
计算的极限系列 http://songshuhui.net/?s=%E5%9B%BE%E7%81%B5%E6%9C%BA
顾森讲解图灵机 http://www.guokr.com/blog/424910/
顾森 http://www.matrix67.com/blog/

图灵机与计算理论 – 集智俱乐部  www.swarma.org/vm/articles/turing.pdf

图灵论文COMPUTING MACHINERY AND INTELLIGENCEhttp://www.loebner.net/Prizef/TuringArticle.html
http://www.readventurer.com/?p=127
Turing机、人工智能以及我们的世界
http://www.matrix67.com/blog/archives/4930

http://www.swarmagents.com/vm/articles/turing.pdf

http://www.swarmagents.com/bs/files/jake2011329111202.pdf

http://v.youku.com/v_show/id_XMjU3NjA4NzU2.html

http://v.youku.com/v_show/id_XMjU3NTgxMTg0.html

王垠:如何掌握程序语言

学习程序语言是每个程序员的必经之路。可是这个世界上有太多的程序语言,每一种都号称具有最新的“特性”。所以程序员的苦恼就在于总是需要学习各种稀奇古怪的语言,而且必须紧跟“潮流”,否则就怕被时代所淘汰。

作为一个程序语言的研究者,我深深的知道这种心理产生的根源。程序语言里面其实有着非常简单,永恒不变的原理。看到了它们,就可以在很短的时间之内就能学会并且开始使用任何新的语言,而不是花费很多功夫去学习一个又一个的语言。

对程序语言的各种误解

学习程序语言的人,经常会出现以下几种心理,以至于他们会觉得有学不完的东西,或者走上错误的道路。以下我把这些心理简要分析一下。

1. 程序语言无用论。这是国内大学计算机系的教育常见的错误。教授们常常对学生灌输:“用什么程序语言不重要,重要的是算法。”而其实,程序语言却是比算法更加精髓的东西。任何算法以及它的复杂度分析,都是相对于某种计算模型,而程序语言就是描述这种计算模型的符号系统。算法必须用某种语言表述出来,通常算法设计者使用伪码,这其实是不严谨的,容易出现推理漏洞。算法设计再好,如果不懂得程序语言的原理,也不可能高效的实现。即使实现了,也可能会在模块化和可扩展性上面有很大问题。某些算法专家或者数学家写出来的程序极其幼稚,就是因为他们忽视了程序语言的重要性。

2. 追求“新语言”。基本的哲学告诉我们,新出现的事物并不一定是“新事物”,它们有可能是历史的倒退。事实证明,新出现的语言,可能还不如早就存在的。其实,现代语言的多少“新概念”不存在于最老的一些语言里呢?程序语言就像商品,每一家都为了拉拢程序员作广告,而它们绝大多数的设计都可能是肤浅而短命的。如果你看不透这些东西的设计,就会被它们蒙蔽住。很多语言设计者其实并不真的懂得程序语言设计的原理,所以常常在设计中重复前人的错误。但是为了推销自己的语言和系统,他们必须夸夸其谈,进行宗教式的宣传。

3. “存在即是合理”。记得某人说过:“不能带来新的思维方式的语言,是没有必要存在的。”他说的是相当正确的。世界上有这么多的语言,有哪些带来了新的思维方式呢?其实非常少。绝大部分的语言给世界带来的其实是混乱。有人可能反驳说:“你怎么能说A 语言没必要存在?我要用的那个库L,别的语言不支持,只能用A。”但是注意,他说的是存在的“必要性”。如果你把存在的“事实”作为存在的“必要性”,那就逻辑错乱了。就像如果二战时我们没能打败希特勒,现在都做了他的奴隶,然后你就说:“希特勒应该存在,因为他养活了我们。”你的逻辑显然有问题,因为如果历史走了另外一条路(即希特勒不存在),我们会过上自由幸福的生活,所以希特勒不应该存在。对比一个东西存在与不存在的两种可能的后果,然后做出判断,这才是正确的逻辑。按照这样的推理,如果设计糟糕的A 语言不存在,那么设计更好的B 语言很有可能就会得到更多的支持,从而实现甚至超越L 库的功能。

4. 追求“新特性”。程序语言的设计者总是喜欢“发明”新的名词,喜欢炒作。普通程序员往往看不到,大部分这些“新概念”其实徒有高深而时髦的外表,却没有实质的内涵。常常是刚学会一个语言A,又来了另一个语言B,说它有一个叫XYZ 的新特性。于是你又开始学习B,如此继续。在内行人看来,这些所谓的“新特性”绝大部分都是新瓶装老酒。很多人写论文喜欢起这样的标题:《XYZ:A Novel Method for …》。这造成了概念的爆炸,却没有实质的进步。

5. 追求“小窍门”。很多编程书喜欢卖弄一些小窍门,教你如何让程序显得“短小”。比如它们会跟你讲 “(i++) –(++i)” 应该得到什么结果;或者追究运算符的优先级,说这样可以少打括号;要不就是告诉你“if 后面如果只有一行代码就可以不加花括号”,等等。殊不知这些小窍门,其实大部分都是程序语言设计的败笔。它们带来的不是清晰的思路,而是是逻辑的混乱和认知的负担。比如C 语言的++ 运算符,它的出现是因为C 语言设计者们当初用的计算机内存小的可怜,而 “i++” 显然比 “i=i+1″ 少2 个字符,所以他们觉得可以节省一些空间。现在我们再也不缺那点内存,可是++ 运算符带来的混乱和迷惑,却流传了下来。现在最新的一些语言,也喜欢耍这种语法上的小把戏。如果你追求这些小窍门,往往就抓不住精髓。

6. 针对“专门领域”。很多语言没有新的东西,为了占据一方土地,就号称自己适合某种特定的任务,比如文本处理,数据库查询,WEB编程,游戏设计,并行计算。但是我们真的需要不同的语言来干这些事情吗?其实绝大部分这些事情都能用同一种通用语言来解决,或者在已有语言的基础上做很小的改动。只不过由于各种政治和商业原因,不同的语言被设计用来占领市场。就学习而言,它们其实是无关紧要的,而它们带来的“学习负担”,其实差不多掩盖了它们带来的好处。其实从一些设计良好的通用语言,你可以学会所有这些“专用语言”的精髓,而不用专门去学它们。

7. 宗教信仰。很多人对程序语言有宗教信仰。这跟人们对操作系统有宗教信仰很类似。其实如果你了解程序语言的本质,就会发现其实完全没必要跟人争论一些事情。某个语言有缺点,应该可以直接说出来,却被很多人忌讳,因为指出缺点总是招来争论和憎恨。这原因也许在于程序语言的设计不是科学,它类似于圣经,它没法被“证伪”。没有任何实验可以一下子断定那种语言是对的,那种是错的。所以虽然你觉得自己有理,却很难让人信服。没有人会去争论哪家的汉堡更好,却有很多人争论那种语言更好。因为很多人把程序语言当成自己的神,如果你批评我的语言,你就是亵渎我的神。解决的办法也许是,不要把自己正在用的语言看得太重要。你现在认为是对的东西,也许不久就会被你认为是错的,反之亦然。

如何掌握程序语言

看到了一些常见的错误心理,那么我们来谈一下什么样的思维方式会更加容易的掌握程序语言。

1. 专注于“精华”和“原理”。就像所有的科学一样,程序语言最精华的原理其实只有很少数几个,它们却可以被用来构造出许许多多纷繁复杂的概念。但是人们往往忽视了简单原理的重要性,匆匆看过之后就去追求最新的,复杂的概念。他们却没有注意到,绝大部分最新的概念其实都可以用最简单的那些概念组合而成。而对基本概念的一知半解,导致了他们看不清那些复杂概念的实质。比如这些概念里面很重要的一个就是递归。国内很多学生对递归的理解只停留于汉诺塔这样的程序,而对递归的效率也有很大的误解,认为递归没有循环来得高效。而其实递归比循环表达能力强很多,而且效率几乎一样。有些程序比如解释器,不用递归的话基本没法完成。

2. 实现一个程序语言。学习使用一个工具的最好的方式就是制造它,所以学习程序语言的最好方式就是实现一个程序语言。这并不需要一个完整的编译器,而只需要写一些简单的解释器,实现最基本的功能。之后你就会发现,所有语言的新特性你都大概知道可以如何实现,而不只停留在使用者的水平。实现程序语言最迅速的方式就是使用一种像Scheme 这样代码可以被作为数据的语言。它能让你很快的写出新的语言的解释器。我的GitHub 里面有一些我写的解释器的例子(比如这个短小的代码实现了Haskell 的lazy 语义)。

几种常见风格的语言

下面我简要的说一下几种常见风格的语言以及它们的问题。

1. 面向对象语言

事实说明,“面向对象”这整个概念基本是错误的。它的风靡是因为当初的“软件危机”(天知道是不是真的存在这危机)。设计的初衷是让“界面”和“实现”分离,从而使得下层实现的改动不影响上层的功能。可是大部分面向对象语言的设计都遵循一个根本错误的原则:“所有的东西都是对象(Everything is an object)。”以至于所有的函数都必须放在所谓的“对象”里面,而不能直接被作为参数或者变量传递。这导致很多时候需要使用繁琐的设计模式(design patterns) 来达到甚至对于C 语言都直接了当的事情。而其实“界面”和“实现”的分离,并不需要把所有函数都放进对象里。另外的一些概念,比如继承,重载,其实带来的问题比它们解决的还要多。

“面向对象方法”的过度使用,已经开始引起对整个业界的负面作用。很多公司里的程序员喜欢生搬硬套一些不必要的设计模式,其实什么好事情也没干,只是使得程序冗长难懂。

那 么如何看待具备高阶函数的面向对象语言,比如Python, JavaScript, Ruby, Scala? 当然有了高阶函数,你可以直截了当的表示很多东西,而不需要使用设计模式。但是由于设计模式思想的流毒,一些程序员居然在这些不需要设计模式的语言里也采用繁琐的设计模式,让人哭笑不得。所以在学习的时候,最好不要用这些语言,以免受到不必要的干扰。到时候必要的时候再回来使用它们,就可以取其精华,去其糟粕。

2. 低级过程式语言

那么是否C 这样的“低级语言”就会好一些呢?其实也不是。很多人推崇C,因为它可以让人接近“底层”,也就是接近机器的表示,这样就意味着它速度快。这里其实有三个问题:

1) 接近“底层”是否是好事?

2)“速度快的语言”是什么意思?

3) 接近底层的语言是否一定速度快?

对于第一个问题,答案是否定的。其实编程最重要的思想是高层的语义(semantics)。语义构成了人关心的问题以及解决它们的算法。而具体的实现(implementation),比如一个整数用几个字节表示,虽然还是重要,但却不是至关重要的。如果把实现作为学习的主要目标,就本末倒置了。因为实现是可以改变的,而它们所表达的本质却不会变。所以很多人发现自己学会的东西,过不了多久就“过时”了。那就是因为他们学习的不是本质,而只是具体的实现。

其次,谈语言的“速度”,其实是一句空话。语言只负责描述一个程序,而程序运行的速度,其实绝大部分不取决于语言。它主要取决于1)算法和2)编译器的质量。编译器和语言基本是两码事。同一个语言可以有很多不同的编译器实现,每个编译器生成的代码质量都可能不同,所以你没法说“A 语言比B 语言快”。你只能说“A 语言的X 编译器生成的代码,比B 语言的Y 编译器生成的代码高效”。这几乎等于什么也没说,因为B 语言可能会有别的编译器,使得它生成更快的代码。

我举个例子吧。在历史上,Lisp 语言享有“龟速”的美名。有人说“Lisp 程序员知道每个东西的值,却不知道任何事情的代价”,讲的就是这个事情。但这已经是很久远的事情了,现代的Lisp 系统能编译出非常高效的代码。比如商业的Chez Scheme 编译器,能在5秒钟之内编译它自己,编译生成的目标代码非常高效。它可以直接把Scheme 程序编译到多种处理器的机器指令,而不通过任何第三方软件。它内部的一些算法,其实比开源的LLVM 之类的先进很多。

另外一些函数式语言也能生成高效的代码,比如OCaml。在一次程序语言暑期班上,Cornell 的Robert Constable 教授讲了一个故事,说是他们用OCaml 重新实现了一个系统,结果发现OCaml 的实现比原来的C 语言实现快了50 倍。经过C 语言的那个小组对算法多次的优化,OCaml 的版本还是快好几倍。这里的原因其实在于两方面。第一是因为函数式语言把程序员从底层细节中解脱出来,让他们能够迅速的实现和修改自己的想法,所以他们能够迅速的找到更好的算法。第二是因为OCaml 有高效的编译器实现,使得它能生成很好的代码。

从上面的例子,你也许已经可以看出,其实接近底层的语言不一定速度就快。因为编译器这种东西其实可以有很高级的“智能”,甚至可以超越任何人能做到的底层优化。但是编译器还没有发展到可以代替人来制造算法的地步。所以现在人需要做的,其实只是设计和优化自己的高层算法。

3. 高级过程式语言

很早的时候,国内计算机系学生的第一门编程课都是Pascal。Pascal 是很不错的语言,可是很多人当时都没有意识到。上大学的时候,我的Pascal 老师对我们说:“我们学校的教学太落后了。别的学校都开始教C 或者C++ 了,我们还在教Pascal。”现在真正理解了程序语言的设计原理以后我才真正的感觉到,原来Pascal 是比C 和C++ 设计更好的语言。它不但把人从底层细节里解脱出来,没有面向对象的思维枷锁,而且有一些很好的设计,比如强类型检查,嵌套函数定义等等。可是计算机的世界真是谬论横行,有些人批评Pascal,把优点都说成是缺点。比如Brain Kernighan 的这篇《Why Pascal is Not My Favorite Programming Language》,现在看来真是谬误百出。Pascal 现在已经几乎没有人用了。这并不很可惜,因为它被错怪的“缺点”其实已经被正名,并且出现在当今最流行的一些语言里:Java, Python, C#, ……

4. 函数式语言

函数式语言相对来说是当今最好的设计,因为它们不但让人专注于算法和对问题的解决,而且没有面向对象语言那些思维的限制。但是需要注意的是并不是每个函数式语言的特性都是好东西。它们的支持者们经常把缺点也说成是优点,结果你其实还是被挂上一些不必要的枷锁。比如  OCaml 和SML,因为它们的类型系统里面有很多不成熟的设计,导致你需要记住太多不必要的规则。

5. 逻辑式语言

逻辑式语言(比如Prolog)是一种超越函数式语言的新的思想,所以需要一些特殊的训练。逻辑式语言写的程序,是能“反向运行”的。普通程序语言写的程序,如果你给它一个输入,它会给你一个输出。但是逻辑式语言很特别,如果你给它一个输出,它可以反过来给你所有可能的输入。其实通过很简单的方法,可以不费力气的把程序从函数式转换成逻辑式的。但是逻辑式语言一般要在“pure”的情况下(也就是没有复杂的赋值操作)才能反向运行。所以学习逻辑式语言最好是从函数式语言开始,在理解了递归,模式匹配等基本的函数式编程技巧之后再来看Prolog,就会发现逻辑式编程简单了很多。

从何开始

可是学习编程总要从某种语言开始。那么哪种语言呢?就我的观点,首先可以从Scheme 入门,然后学习一些Haskell (但不是全部),之后其它的也就触类旁通了。你并不需要学习它们的所有细枝末节,而只需要学习最精华的部分。所有剩余的细节,会在实际使用中很容易的被填补上。现在我推荐几本比较好的书。

《The Little Schemer》(TLS):我觉得Dan Friedman 的The Little Schemer 是目前最好,最精华的编程入门教材。这本书很薄,很精辟。它的前身叫《The Little Lisper》。很多资深的程序语言专家都是从这本书学会了Lisp。虽然它叫“The Little Schemer”,但它并不使用Scheme 所有的功能,而是忽略了Scheme 的一些毛病,直接进入最关键的主题:递归和它的基本原则。

《Structure and Interpretation of Computer Programs | 计算机程序的构造和解释》(SICP):The Little Schemer 其实是比较难的读物,所以我建议把它作为下一步精通的读物。SICP 比较适合作为第一本教材。但是我需要提醒的是,你最多只需要看完前三章。因为从第四章开始,作者开始实现一个Scheme 解释器,但是作者的实现并不是最好的方式。你可以从别的地方更好的学到这些东西。不过也许你可以看完SICP 第一章之后就可以开始看TLS。

《A Gentle Introduction to Haskell》:对于Haskell,我最开头看的是A Gentle Introduction to Haskell,因为它特别短小。当时我已经会了Scheme,所以不需要再学习基本的函数式语言的东西。我从这个文档学到的只不过是Haskell 对于类型和模式匹配的概念。

过度到面向对象语言

那么如果从函数式语言入门,如何过渡到面向对象语言呢?毕竟大部分的公司用的是面向对象语言。如果你真的学会了函数式语言,就会发现面向对象语言已经易如反掌。函数式语言的设计比面向对象语言简单和强大很多,而且几乎所有的函数式语言教材(比如SICP)都会教你如何实现一个面向对象系统。你会深刻的看到面向对象的本质以及它存在的问题,所以你会很容易的搞清楚怎么写面向对象的程序,并且会发现一些窍门来避开它们的局限。你会发现,即使在实际的工作中必须使用面向对象语言,也可以避免面向对象的思维方式,因为面向对象的思想带来的大部分是混乱和冗余。

深入本质和底层

那么是不是完全不需要学习底层呢?当然不是。但是一开头就学习底层硬件,就会被纷繁复杂的硬件设计蒙蔽头脑,看不清楚本质上简单的原理。在学会高层的语言之后,可以进行“语义学”和“编译原理”的学习。

简言之,语义学(semantics) 就是研究程序的符号表示如何对机器产生“意义”,通常语义学的学习包含lambda calculus 和各种解释器的实现。编译原理(compilation) 就是研究如何把高级语言翻译成低级的机器指令。编译原理其实包含了计算机的组成原理,比如二进制的构造和算术,处理器的结构,内存寻址等等。但是结合了语义学和编译原理来学习这些东西,会事半功倍。因为你会直观的看到为什么现在的计算机系统会设计成这个样子:为什么处理器里面有寄存器(register),为什么需要堆栈(stack),为什么需要堆(heap),它们的本质是什么。这些甚至是很多硬件设计者都不明白的问题,所以它们的硬件里经常含有一些没必要的东西。因为他们不理解语义,所以经常不明白他们的硬件到底需要哪些部件和指令。但是从高层语义来解释它们,就会揭示出它们的本质,从而可以让你明白如何设计出更加优雅和高效的硬件。

这就是为什么一些程序语言专家后来也开始设计硬件。比如Haskell 的创始人之一Lennart Augustsson 后来设计了BlueSpec,一种高级的硬件描述语言,可以100% 的合成(synthesis) 为硬件电路。Scheme 也被广泛的使用在硬件设计中,比如Motorola, Cisco 和曾经的Transmeta,它们的芯片设计里面含有很多Scheme 程序。

这基本上就是我对学习程序语言的初步建议。以后可能会就其中一些内容进行更加详细的阐述。

 

转自:http://www.2cto.com/kf/201208/147722.html