近来读叶嘉莹先生的《人间词话七讲》,发觉第六讲中先生对“无奈朝来寒雨晚来风”一句解析有误。叶先生说中国古诗词中但凡朝暮对举,就是朝朝暮暮;风雨对举,就是风风雨雨[1],其实道理并非如此。比如朝秦暮楚,就不是说朝朝暮暮追随秦楚;朝三暮四,也不是说朝朝暮暮三三四四。

“朝来寒雨晚来风”用到了汉语中的一种修辞——互文。百度百科的解释是:“互文,也叫互辞,是古诗文中常采用的一种修辞方法。古文中对它的解释是:‘参互成文,含而见文。’具体地说,它是这样一种互辞形式:上下两句或一句话中的两个部分,看似各说两件事,实则是互相呼应,互相阐发,互相补充,说的是一件事。由上下文义互相交错,互相渗透,互相补充来表达一个完整句子意思的修辞方法。”我认为基本讲得在理。

譬如,“烟笼寒水月笼沙”是说烟与月笼罩水与沙,“秦时明月汉时关”说的是秦汉时的关山,“将军白发征夫泪”说的是将军和征夫的白发与泪。呃写到这里发现我举的例子竟然和百度百科一样,只能说这几句互文过于经典。

为什么要用互文呢?互文可以用精简的句子表达丰富的含义。如果对于互文,我们只理解了字面意思,那很可能是狭隘而说不通的。比如“东市买骏马,西市买鞍鞯,南市买辔头,北市买长鞭。”难道真的那么巧每个超市买一样?其实就是说木兰君到处逛街终于把东西买到了,用对称铺叠的句子写出来,不仅文字精简,而且可以增加诗歌的美感。再比如《项脊轩志》“东犬西吠”,高中语文书上说“东家的狗(听到西家的声音)就对着西家叫。”这脑补得实在有些厉害,也根本讲不通。归有光其实只是说到处都有狗叫而已。《琵琶行》“主人下马客在船”,说的是主人和客人一起下马上船,如果解释成主人下马,客人在船上,那就说不通了。如果是主人送客而主人并没有上船的话,那何来“移船相近邀相见,添酒回灯重开宴”?如果主人是牵马去江边迎客,那又何来序文中“送客湓浦口”一说?不能读出互文,很多作品就理解不了。

新课标人教版中学语文书中对于古诗文的注疏,是有很多问题的。

[1] “中国的诗词凡是在对举的时候,朝暮的对举,就是朝朝暮暮;风雨的对举,就是雨雨风风。”——叶嘉莹《人间词话七讲》第六讲,139页,北京大学出版社。

我中学用过很多 Linux 发行版,在我中学尝试的诸多版本中,印象最好,使用最长的是国人制作的 Magic Linux。

我今天发现,这个版本居然还在维护,而且在今年7 月发出了 6 年来的第一次版本更新:http://www.magiclinux.org/ 这让我非常怀念,也非常开心。

Magic Linux 是一款国人制作的 Linux 发行版,对中国人非常友好。在那个上古年代,Linux 发行版对中文的支持很差,字体错乱,还经常有乱码。那个时候 Red Hat 还没有启用yum,我还没接触 Debian 系,不知道 apt。软件仓库这件事无从谈起,rpm 包也常不兼容,每次安装软件,都会遭遇巨大的痛苦,不仅要自己编译、make,还要读懂各种报错信息,去 sourceforge 下载.lib .so 依赖包,再把它们安装到合适的位置,简直不能再痛苦。那时的国际化 Linux 版本也很少有为中国人订制的软件,办公软件水土不服,不少工具汉化不完整。音频视频播放器这种桌面常见应用用起来也不方便,因为 Linux 的版权限制,MP3 等编码的解析器是不能捆绑在发行版里的,需要用户自己去安装。而那时候大多数系统上并没有软件仓库,安装难度可想而知。当时 rmvb 和 rm 这种古董级格式还非常流行,由于这个格式是 reaplayer 的私家标准,尤其难办。

Magic Linux 把这些问题都改进了,在 2005-2006 年那个年代,它就提供了一个软件管理程序,虽然没有 apt 那么完备,但是已经很有软件仓库的影子。即便我要安装仓库中没有的程序,它也能以更友好的方式向我提示依赖。Magic Linux 提供了 C++写成的 Eva,可以在 Linux 系统下使用 QQ,是我在 Linux 下使用时间最长的第三方QQ客户端。QQ 为了封禁这些第三方客户端,会经常修改通信协议,Eva 坚挺了很久,使用体验也非常好,性能卓越,背后一定有很多贡献者付出了大量的心血。最终 Eva 还是没能坚持开发下来,彻底登不了 QQ 了。音频视频播放器的解码器也有很好的傻瓜式解决方案。令人惊喜的是,它还自带了一个游戏大厅,像腾讯游戏大厅那样可以打牌玩,可惜我登录过几次,里面根本就没有人,码农真是苦逼啊。顺便吐槽一句,QQ 现在越来越慢了,2008 年的那个 QQ 呢?!

国人开发的 Linux 版本也有不少,包括中科院专资开发的红旗 Linux。我用过红旗 4.0 和红旗 5.0,比 Magic Linux 差多了,桌面应用和开发程序都很不方便,倒是外形是我见过的 Linux 中长的最像 Windows 的,连“开始”菜单都 cosplay 了一个,简直哭瞎。现在这个项目已经倒闭,项目员工集体举牌讨薪,我说当年大家如果用点功,也不至于是这个结局…… Magic Linux 要比其他官方赞助的版本优秀多了。

2008 年以后,似乎团队不再维护 Magic Linux,系统从内核到各种库都得不到更新,我也从此改用 Ubuntu8.04 和 Ubuntu8.10,开启了 apt 和“新立得”的幸福生活。

如今“新立得”也早已不见踪迹,Ubuntu 简直变得和 Windows 一样好用。时代真是在进步,当码农越来越容易了。

附 Eva 开源项目 github 地址:https://github.com/MagicGroup/eva

1947 年的铜陵汀洲,是个老师很难生存的地方。

当地家长都很有文化,总嫌弃老师水平差。老师一旦教错,家长就要起哄。

邓老师要靠教书的薪水养足一双儿女,还要天天受家长的学术质疑,内外交困,请了辞。他后来的人生看起来很悲惨,丢了教职以后,一路乘船北上,赶赴妻子的老家天津讨生活。路上又丢了一个孩子。他很怀念故乡,多年以后,回到了铜陵。为了回家,他在路中变卖了所有的行李,回家时已经一无所有,后来怎么样我不知道。

邓老师辞职后留下了一个缺,而外公当时在家赋闲,小学校长听说了,便要请外公去执教。

定教职是需要面试的,校长听课,外公试讲。第一节课讲六年级语文,第二节课讲五年级数学。讲完,午饭,饭中校长就双手捧过了高级教师聘书。在传统的年代,人们的礼数比现在更为繁复,当场录用为高级教师,并且双手捧过聘书,是很大的尊重和肯定。十年前,九十多岁的老校长还给外公送了一幅字,苏轼的《水调歌头》《念奴娇》两首。就一直挂在墙上,外公也不装裱,宣纸已经发黄。我无数次看过这幅字,写得非常漂亮,可惜我手头没有好照片。如今这幅字已经被新的字画盖住,拍起来很麻烦。

高级教师就可以当班主任了,可是这班主任并不好当,因为 1947 年的铜陵汀洲,是个老师很难生存的地方。

有一回外公批国文书法作业,给一位学生的“達”字画了一个圈,以示好评。当时大家还是都用繁体字的,“達”字,是“幸”字下加一横再添走之。可是这位学生却写成了“幸”字加走之,少了一横。家长一见,非常生气,说白字先生乱教书,不仅看不出错字,还给错字画圈。

外公脾气很大,没多久就跟校长说:“我不干了。”校长觉得纳闷,“你不是做得好好的吗?怎么突然就不干了?”外公说:“我给学校丢了人,呆不住了,学生家长不满意。”校长说:“没哪个跟我讲过啊。”外公这才一五一十把事情说了。原来,柳宗元写书法的时候,就给“達”少写了一横,所以书法上少一横不能算错,顶多是个异体字。现代人写简化字写久了不熟悉,在当时这都是广为接受的概念。

于是校长不答应了,他把这件事告诉了乡议员,说这个家长无理取闹。乡议员说这成何体统,要求家长必须检讨,要办酒道歉。那个时候,乡中给老师道歉,要办酒席,放爆竹,让全乡知晓,当众致歉,以示尊师。家长一听乡议员说是他自己搞错了,立马表示道歉,筹备酒席,毫不含糊。那一天外公没去酒席,因为他自认为脾气不好,如果去了一定会教育那位家长,溯清“達”字源流,这样两边都很尴尬。所以当天由校长代行受礼,放爆竹,设酒席,宴同乡,学校名声得以昌隆,乡民对外公也就服气了。

1947 年的铜陵汀洲,是个很热爱知识文化而又不叶公好龙的地方。

V 社大良心,制作了 Steam 这个跨平台游戏中心,提供的 source 引擎也是跨平台的。所以,我们只需要在 Ubuntu 软件仓库中安装 Steam ,就可以玩 Steam 中的游戏啦。

在软件仓库里,我们先要点击“购买”按钮购买 Steam,然后切入 Ubuntu One 的认证页面进行认证,认证完毕,就可以以 0 元的价格买入 Steam 了,此时下载安装,和普通软件包没有区别。

启动 Steam 后,找到 Dota, 下载安装。启动 Dota 后,发现只能连接到世界服,有东南亚区、欧洲区、美国区等等。至于中国区,你懂的。为了取得更快的连接速度和更好的游戏体验,我们需要连接到完美世界代理的国服。在 Steam 中右击 Dota2,点击“属性”,“设置启动选项……”,在弹出的对话框中输入“ -perfectworld steam ”。再启动 Dota2 时,连接的就是完美世界了。我体验了一把,感觉和 Windows7 下运行没什么区别,一样一样的。赞!

由于 expressjs 自带的 body-parser 默认不能解析 ‘text/xml’ 的内容,我曾考虑依照 body-parser 本身的结构自己写一个工业级的 ‘text/xml’ 解析器。后来才发现,其实可以通过调用 body-parser 的 text() 函数作为中间件,对 ‘text/xml’ 解析,只要在赋入的选项中添加 type: ‘text/xml’ 属性即可。我自己写的 ‘text/xml’ 解析器算是个副产品吧,有时间测试后也会发表,比直接调用 bodyParser.text() 在功能上要强一些,流程上也统一一些,安全性也高一些。现有的软件库中我还没有看到具有类似功能的模块。

参考代码 1: expressjs 项目的入口,载入 body-parser 模块并调用 text() 中间件,如果不赋入 ‘text/xml’ 选项,text() 将默认以 ‘text/plain’ 类型执行解析,则会发生类型匹配错误,导致解析无法完成,所以 ‘text/xml’ 选项是必须手动传入的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Module dependencies.
*/
var express = require('express');
var routes = require('./routes');
var user = require('./routes/user');
var http = require('http');
var path = require('path');
// 载入 body-parser 模块,expressjs自带的部分没有 text() 函数。
var bodyParser = require ('body-parser');
var app = express();
// all environments
app.set('port', process.env.PORT || 3000);
app.set('views', path.join(__dirname, 'views'));
app.set('view engine', 'jade');
app.use(express.favicon());
app.use(express.logger('dev'));
// 将请求体中的 xml 解析为字符串。
app.use(bodyParser.text({type: 'text/xml'}));
app.use(express.json());
app.use(express.urlencoded());
app.use(express.methodOverride());
app.use(app.router);
app.use(express.static(path.join(__dirname, 'public')));
// development only
if ('development' == app.get('env')) {
app.use(express.errorHandler());
}
app.get('/', routes.index);
app.get('/users', user.list);
http.createServer(app).listen(app.get('port'), function(){
console.log('Express server listening on port ' + app.get('port'));
});

参考代码 2:通过 xml2js 将解析出的 xml 字符串解析为 json ,并存入解析完成后的请求体中供其他代码调用。

1
2
3
4
5
6
7
8
9
10
11
12
{parseString} = require 'xml2js'
exports.index = (req, res) ->
parseString req.body, (err, result) ->
if err
err.status = 400
res.end 'error'
return
else
req.body = result
console.log req.body
res.end 'success'
return

由于需要在 expressjs 中解析 xml ,而 expressjs 默认无法解析 xml 。所以我打算自己造一个工业级轮子,于是参考了 expressjs 中关于 json 解析方面的代码。代码分析如是。

朴素实现是监听 req 的 data 事件,将读到的数据存储在字符串变量中再进行解析。body-parser 的实现与此有不少区别。首先,代码中有很多校验信息,要根据请求头中的内容对请求体做类型、长度、字符编码等校验,以此提高安全性;其次,代码都是通过调用 raw-body 模块中的 getRawBody(stream, options, callback) 来解析请求体的,而不是直接监听 data 事件进行操作。getRawBody 函数会做请求体校验、异常处理、管道卸载等工作,比朴素的做法安全很多。 getRawBody 函数也可以完成解码功能。

body-parser 的文档和代码见: https://github.com/expressjs/body-parser 。中文注释为我的注析。这里只解析 index.js 及其调用的内容, lib/types/ 下的其他文件结构类似,忽略不析。

index.jslink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*!
* body-parser
* Copyright(c) 2014 Douglas Christopher Wilson
* MIT Licensed
*/
/**
* Module dependencies.
*/
// deprecate 是一个用来显示“不建议”消息的工具,可以用来警告用户不要使用
// 那些不建议使用的函数或模块。详见:
// https://github.com/dougwilson/nodejs-depd
var deprecate = require('depd')('body-parser')
var fs = require('fs') // 载入文件处理模块,nodejs 核心模块。
// 载入路径处理模块,nodejs 核心模块,参考:
// http://nodejs.org/api/path.html
var path = require('path')
/**
* Module exports.
*/
exports = module.exports = deprecate.function(bodyParser,
'bodyParser: use individual json/urlencoded middlewares')
/**
* Path to the parser modules.
*/
var parsersDir = path.join(__dirname, 'lib', 'types')
/**
* Auto-load bundled parsers with getters.
*/
//遍历 /lib/types 目录下的文件。
fs.readdirSync(parsersDir).forEach(function onfilename(filename) {
if (!/\.js$/.test(filename)) return //如果文件不是 .js 文件,返回。
var loc = path.resolve(parsersDir, filename) // 提取文件的绝对位置。
var mod
var name = path.basename(filename, '.js') // 提取文件的基础名。
function load() {
if (mod) {
return mod
}
// 载入位于loc位置的文件,由于load函数可能在其他地方被调用,所以这里
// loc 记录的是绝对位置,增强代码的可移植性。
return mod = require(loc)
}
// 给 exports 添加一个新的属性 name,代码还设置了 name 属性的三个属性
// 描述符。关于 Object.defineProperty ,详见:
// https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Object/defineProperty
Object.defineProperty(exports, name, {
configurable: true, // 使 name 属性可以被改变。
enumerable: true, // 使 name 属性可枚举。
get: load // 使 name 属性有 getter 方法。
})
})
/**
* Create a middleware to parse json and urlencoded bodies.
*
* @param {object} [options]
* @return {function}
* @deprecated
* @api public
*/
function bodyParser(options){
var opts = {}
options = options || {} // 初始化 options 。
// exclude type option
for (var prop in options) {
if ('type' !== prop) {
opts[prop] = options[prop]
}
}
var _urlencoded = exports.urlencoded(opts)
var _json = exports.json(opts)
return function bodyParser(req, res, next) {
_json(req, res, function(err){ // 将请求体解析为 json 。
if (err) return next(err);
// 如果请求体不是 json ,则将其解析为 urlencoded 内容。
_urlencoded(req, res, next);
});
}
}
lib/types/json.jslink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*!
* body-parser
* Copyright(c) 2014 Jonathan Ong
* Copyright(c) 2014 Douglas Christopher Wilson
* MIT Licensed
*/
/**
* Module dependencies.
*/
// bytes 模块可以在字节度量的数字表示和字符串表示之
// 间互相转换。例如:
// bytes('1kb') 结果为 1024 ;
// bytes('2mb') 结果为 2097152 ;
// bytes('1gb') 结果为 1073741824 ;
// bytes(1073741824) 结果为 1gb ;
// bytes(1099511627776) 结果为 1tb 。
// 详见 github 上的 visionmedia/bytes.js 项目:
// https://github.com/visionmedia/bytes.js
var bytes = require('bytes')
var read = require('../read')
// expressjs 自带的媒体解析模块,详见:
// https://github.com/expressjs/media-typer
var typer = require('media-typer')
// type-is 是 expressjs 自带的类型判断模块,详见 github 上的 expressjs/
// type-is 项目: https://github.com/expressjs/type-is
var typeis = require('type-is')
/**
* Module exports.
*/
module.exports = json
/**
* RegExp to match the first non-space in a string.
*/
var firstcharRegExp = /^\s*(.)/
/**
* Create a middleware to parse JSON bodies.
*
* @param {object} [options]
* @return {function}
* @api public
*/
function json(options) {
options = options || {}
var limit = typeof options.limit !== 'number'
? bytes(options.limit || '100kb')
: options.limit // 设置解析请求体长度上限。
var inflate = options.inflate !== false // 设置是否要将压缩的请求体解压。
var reviver = options.reviver // 传递给 JSON.parse() 的参数。
var strict = options.strict !== false // 设置是否只解析对象和数组。
var type = options.type || 'json' // 设置解析的请求体内容类型。
var verify = options.verify || false // 设置请求体内容验证函数。
if (verify !== false && typeof verify !== 'function') {
throw new TypeError('option verify must be function')
} // 请求体的内容验证函数必须是一个函数。
function parse(body) {
if (0 === body.length) {
throw new Error('invalid json, empty body')
}
if (strict) {
var first = firstchar(body) // firstchar 函数的定义在116行。
if (first !== '{' && first !== '[') {
throw new Error('invalid json')
}
}
// 解析 body ,详见:
// https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/JSON/parse
return JSON.parse(body, reviver)
}
// 返回解析函数作为 expressjs 的中间件。
return function jsonParser(req, res, next) {
// req._body 标记着请求体是否已被解析,若 req._body 为 true ,则请求体
// 已被解析。
if (req._body) return next()
req.body = req.body || {}
// 检测请求体是否与 type 类型匹配。
if (!typeis(req, type)) return next()
// RFC 7159 sec 8.1
var charset = typer.parse(req).parameters.charset || 'utf-8'
if (charset.substr(0, 4).toLowerCase() !== 'utf-') {
var err = new Error('unsupported charset')
err.status = 415
next(err)
return
}
// read
read(req, res, next, parse, {
encoding: charset,
inflate: inflate,
limit: limit,
verify: verify
})
}
}
/**
* Get the first non-whitespace character in a string.
*
* @param {string} str
* @return {function}
* @api public
*/
function firstchar(str) {
if (!str) return ''
// 见第 40 行,匹配字符串中第一个非空字符。
var match = firstcharRegExp.exec(str)
return match ? match[1] : ''
}
lib/read.jslink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/*!
* body-parser
* Copyright(c) 2014 Douglas Christopher Wilson
* MIT Licensed
*/
/**
* Module dependencies.
*/
// 将流中的所有内容载入为 buffer 或字符串。参考:
// https://github.com/stream-utils/raw-body
var getBody = require('raw-body')
// 互相转换 buffer 与 js 字符串。参考 github:
// https://github.com/ashtuchkin/iconv-lite
var iconv = require('iconv-lite')
// 使得程序可以在退出时执行一个回调函数。参考:
// https://github.com/jshttp/on-finished
var onFinished = require('on-finished')
// expressjs 自带的媒体解析模块,详见 github:
// https://github.com/expressjs/media-typer
var typer = require('media-typer')
// nodejs 核心模块,提供数据压缩和解压功能。参考:
// http://nodejs.org/api/zlib.html
var zlib = require('zlib')
/**
* Module exports.
*/
module.exports = read
/**
* Read a request into a buffer and parse.
*
* @param {object} req
* @param {object} res
* @param {function} next
* @param {function} parse
* @param {object} options
* @api private
*/
function read(req, res, next, parse, options) {
var length
var stream
// flag as parsed
req._body = true
try {
stream = contentstream(req, options.inflate) // 见第 129 行。
length = stream.length
delete stream.length
} catch (err) {
return next(err)
}
options = options || {} // 初始化 options 。
options.length = length
var encoding = options.encoding !== null
? options.encoding || 'utf-8'
: null
var verify = options.verify
options.encoding = verify
? null
: encoding
// read body
getBody(stream, options, function (err, body) {
if (err) {
if (!err.status) {
err.status = 400
}
// read off entire request
stream.resume()
onFinished(req, function onfinished() {
next(err)
})
return
}
// verify
if (verify) {
try {
verify(req, res, body, encoding)
} catch (err) {
if (!err.status) err.status = 403
return next(err)
}
}
// parse
try {
body = typeof body !== 'string' && encoding !== null
? iconv.decode(body, encoding) // 将请求体解码为 js 字符串。
: body
req.body = parse(body)
} catch (err) {
if (!err.status) {
err.body = body
err.status = 400
}
return next(err)
}
next()
})
}
/**
* Get the content stream of the request.
*
* @param {object} req
* @param {boolean} [inflate=true]
* @return {object}
* @api private
*/
// inflate 表示是否给数据解压缩。
function contentstream(req, inflate) {
// req.headers 是 http 请求的请求头,详细参数见:
// http://www.w3cschool.cc/http/http-header-fields.html
// identity 代表没有压缩编码,见 RFC 7231 , sec 3.1.2.2 。
var encoding = req.headers['content-encoding'] || 'identity'
var err
var length = req.headers['content-length'] // 见 RFC 7230 , sec 3.3.2 。
var stream
if (inflate === false && encoding !== 'identity') {
err = new Error('content encoding unsupported')
err.status = 415
throw err
}
// 参考 zlib 文档: http://nodejs.org/api/zlib.html 。
switch (encoding) {
case 'deflate':
stream = zlib.createInflate()
req.pipe(stream)
break
case 'gzip':
stream = zlib.createGunzip()
req.pipe(stream)
break
case 'identity':
stream = req
stream.length = length
break
default:
err = new Error('unsupported content encoding')
err.status = 415
throw err
}
return stream
}
lib/types/urlencoded.jslink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
/*!
* body-parser
* Copyright(c) 2014 Jonathan Ong
* Copyright(c) 2014 Douglas Christopher Wilson
* MIT Licensed
*/
/**
* Module dependencies.
*/
var bytes = require('bytes')
var deprecate = require('depd')('body-parser')
var read = require('../read')
var typer = require('media-typer')
var typeis = require('type-is')
/**
* Module exports.
*/
module.exports = urlencoded
/**
* Cache of parser modules.
*/
var parsers = Object.create(null)
/**
* Create a middleware to parse urlencoded bodies.
*
* @param {object} [options]
* @return {function}
* @api public
*/
// 详见: https://github.com/expressjs/body-parser#bodyparserurlencodedoptions 。
function urlencoded(options){
options = options || {};
// notice because option default will flip in next major
if (options.extended === undefined) {
deprecate('undefined extended: provide extended option')
}
var extended = options.extended !== false // 是否采用 qs 模块解析 url 编码。
var inflate = options.inflate !== false
var limit = typeof options.limit !== 'number'
? bytes(options.limit || '100kb')
: options.limit
var type = options.type || 'urlencoded'
var verify = options.verify || false
if (verify !== false && typeof verify !== 'function') {
throw new TypeError('option verify must be function')
}
// 选择解析器。
var queryparse = extended
? extendedparser(options)
: simpleparser(options)
function parse(body) {
return body.length
? queryparse(body)
: {}
}
return function urlencodedParser(req, res, next) {
if (req._body) return next();
req.body = req.body || {}
if (!typeis(req, type)) return next();
var charset = typer.parse(req).parameters.charset || 'utf-8'
if (charset.toLowerCase() !== 'utf-8') {
var err = new Error('unsupported charset')
err.status = 415
next(err)
return
}
// read
read(req, res, next, parse, {
encoding: charset,
inflate: inflate,
limit: limit,
verify: verify
})
}
}
/**
* Get the extended query parser.
*
* @param {object} options
*/
// 利用 qs 模块解析 url ,详见: https://github.com/hapijs/qs 。
function extendedparser(options) {
var parameterLimit = options.parameterLimit !== undefined
? options.parameterLimit
: 1000
var parse = parser('qs')
if (isNaN(parameterLimit) || parameterLimit < 1) {
throw new TypeError('option parameterLimit must be a positive number')
}
if (isFinite(parameterLimit)) {
parameterLimit = parameterLimit | 0
}
return function queryparse(body) {
if (overlimit(body, parameterLimit)) {
var err = new Error('too many parameters')
err.status = 413
throw err
}
return parse(body, {parameterLimit: parameterLimit})
}
}
/**
* Determine if the parameter count is over the limit.
*
* @param {string} body
* @param {number} limit
* @api private
*/
function overlimit(body, limit) {
if (limit === Infinity) {
return false
}
var count = 0
var index = 0
while ((index = body.indexOf('&', index)) !== -1) {
count++
index++
if (count === limit) {
return true
}
}
return false
}
/**
* Get parser for module name dynamically.
*
* @param {string} name
* @return {function}
* @api private
*/
function parser(name) {
var mod = parsers[name]
if (mod) {
return mod.parse
}
// load module
mod = parsers[name] = require(name)
return mod.parse
}
/**
* Get the simple query parser.
*
* @param {object} options
*/
function simpleparser(options) {
var parameterLimit = options.parameterLimit !== undefined
? options.parameterLimit
: 1000
// 调用 nodejs 核心模块 querystring 解析 url 。详见:
// http://nodejs.org/api/querystring.html
var parse = parser('querystring')
if (isNaN(parameterLimit) || parameterLimit < 1) {
throw new TypeError('option parameterLimit must be a positive number')
}
if (isFinite(parameterLimit)) {
parameterLimit = parameterLimit | 0
}
return function queryparse(body) {
if (overlimit(body, parameterLimit)) {
var err = new Error('too many parameters')
err.status = 413
throw err
}
return parse(body, undefined, undefined, {maxKeys: parameterLimit})
}
}

由于甲骨文公司的版权限制,Linux 发行版不能包含 Oracle Java,Ubuntu 也只提供了开源的 OpenJDK。OpenJDK 会带来各种各样的兼容性问题,不推荐部署 Java 开发。甲骨文 Oracle Java 本身既包含 JRE(Java Runtime Environment Java 运行环境)又包含 JDK(Java Development Kit Java 开发套件),我们只需要安装一份 Oracle Java 8,即可满足需要。

对于 Ubuntu 及其衍生版,使用 PPA 软件仓库安装 Oracle Java 8 是最快捷的,在终端中输入命令如下即可完成安装:

1
2
3
sudo apt-get repository ppa : webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer

下面这条命令可以设置环境变量,将 Oracle Java 8 设置为系统的默认 Java 虚拟机:

1
sudo apt-get install oracle-java8-set-default

完成以上步骤之后你可以通过下面这行命令检验是否安装成功:

1
java –version

如果安装成功,终端会得到如下提示:

1
2
3
java version “1.8.0”
Java (TM) SE Runtime Environment (build 1.8.0–b132)
Java HotSpot (TM) 64-Bit Server VM (build 25.0–b70, mixed mode)

具体显示的版本号可能会略有不同,例如,32 位机器上会显示 32 位虚拟机的相关信息。

新媒体的语言

列夫·曼诺维奇著
OrangeCLK 译
orangeclk[at]orangeclk.com

引言

现状的理论

我奢望人们在 1895 年或者 1897 年,最晚 1903 年,就能够认识到电影出现的重要性,然后对这个新型媒体的产生过程做下完备的记录。记录包括观众访谈会;逐年发展的叙事手法、场景调度、机位设置;对于新生的电影语言和其他与之共生的娱乐活动之间联系的分析等。不幸的是,这些记录都不存在。相反,我们只有些纸媒报道、电影发明人的日记、影片播放流程,还有些其他散落各处的星星点点。

现在我们正在见证一种全新媒体的出现——数字计算机的元媒体。和100年前电影面世不同,我们现在完全能体会到新媒体革命的巨大影响。但我仍然担心,我们留给未来理论学者与历史学者的资料,就如同电影年代留给我们的纸媒报道和播放流程那样,信息量并没有多多少。未来的学者会发现我们这个年代的分析文章已经充分意识到了计算机对文化的重要影响,但是大部分内容都是对未来的预测而不是对现状理论的记录。未来的研究人员会疑惑,为什么我们这个时代的理论学者,已经拥有了大量分析历史文化形态的经验,却没有努力把计算机媒体的符号代码、寻址模式、用户接纳模式记录下来?电影艺术从全景摄影、光学玩具、西洋镜等上个时代的艺术形式中脱颖而出,我们煞费苦心才还原出这段历史。在计算机媒体语言刚刚诞生的此时此刻,已有文化形式的元素正在逐渐介入计算机媒体。这个过程在我们的时代如此清晰,这些元素还都一一可见,还没有融为新的一体,那么我们为什么不尝试去构建一个类似于电影发展史的计算机媒体发展谱系呢?在多媒体界面的图标和按钮还都像油漆未干的油画笔触时,在他们演变为普遍规范并迅速消失淘汰之前,我们的理论学者在哪里?当神秘岛[1]的设计者调试代码,把图片转化为字节,美化每一帧 QuickTime[2]剪辑画面的时候,我们的理论学者在哪里?有一天,网景公司一位二十来岁的程序员吐出口香糖,啜下一小口温暖的可乐。他已经在计算机前连续工作了16个小时,正努力赶上产品开发的截止日期。最终他以满意的文件大小,制作了一小段星星飞过夜空的动画。在这个历史性的时刻,我们的理论学者在哪里?这段动画就是网景网景导航者[3]右上角的标识,在下一版网景导航者发布之前,它就是世界上观众最多的动画短片。

[1]Myst Cyan公司于1993年推出的一款图形解谜游戏。——译者注
[2]苹果公司的一款媒体播放器。——译者注
[3]网景导航者(Netscape Navigator)又称领航员,是网景公司开发的网络浏览器。曾经是世界上最流行的网页浏览器。——译者注

下面我就要尝试着记录现状,描述现状的理论。就像电影史学者在电影诞生的头几十年跟踪电影语言的发展那样,我想描述并理解新媒体语言发展的动力源泉。(我并不是说新媒体只有一种语言,而是采用这个泛用术语来指代新媒体对象的设计者们采取的种种规范,这些规范用于组织数据和构建用户体验等方面。)进一步类比,电影语言在 1910 年代形成了自己的经典范式,那么现在新媒体语言是否正在接近自己最终稳定的形式呢?这项预测对我很有吸引力。因为未来计算机媒体的语言会和现在的样子完全不同,1990 年的状况可能更接近1890年而非将来的经典范式。

现状在飞速变化,我们针对现状构建理论有意义吗?我只能说这是场糟糕的赌博。如果将来的发展证明我的理论预计是正确的,我就赢了。但是如果计算机媒体语言的发展方向和我分析揭露的方向不同,我的分析就成为来未来人眼中历史发展一种可能性的记录,我们现在可以见到但是未来人难以相信。

我们现在认为电影不会走向单一语言形式,电影不会只走向虚拟现实。相反,我们已经看到电影发展出了多种多样有表达力的成功语言形式。每一种语言都有它自己的美学变量,每一种新语言都导致了一些旧语言的消亡。(这个文化逻辑和托马斯·库恩关于科学范式的分析不同)[4]相似的,计算机媒体历史的每一步都产生了新的美学机遇,包括他们自己对于未来的计划,即他们自己的“研究范式”。这本身也是一种新的语言。研究范式在发展中不断被修正和取代。本书中,我会趁着新媒体研究范式改变之前,在它发展的头几十年记录它们。

[4] Thomas S. Kuhn, The Structure of Scientific Revolutions. 2nd ed. (Chicago: University of Chicago Press, 1970)——作者注

草绘新媒体:方法

本书中,我会在现代视觉和媒体文化的历史背景下对新媒体语言展开分析。新媒体是怎样依赖传统文化形式的?新媒体又是怎样从传统文化形式中分离的?新媒体有什么独特的手法来构建现实、面向用户、表达时间和空间?诸如矩形画面、移动视角、蒙太奇这些传统媒体的惯例和技术在新媒体上是怎样实现的?如果我们想做一次考据,把新的计算机媒体技术和旧的表征仿真技术联系起来,我们应该怎样界定重大的历史突破?

为了回答这些问题,我观察了新媒体的若干领域:网站、虚拟世界[5]、虚拟现实、多媒体、电子游戏、交互设备、计算机动画、数字视频、电影、人机界面等。虽然本书的重点在于陈述理论观点和历史结论,我还是会分析很多领域内关键的历史性新媒体对象。从美国商业经典到国际新媒体艺术家和收藏者,我都会有所涉猎。前者包括神秘岛、毁灭战士[6]、侏罗纪公园、泰坦尼克号等。后者包括 ART+COM、Antirom、jodi.org、George Legrady、Olga Lialina、Jeffrey Shaw、Tamas Waliczky 等。

[5]这里“虚拟世界”指计算机生成的三维互动环境。这个定义适用于所有现在已经面世的三维计算机环境,包括:高档的虚拟现实环境,它们配有头戴式显示器和现实图像的照片;街机、CD光盘、在线多人电子游戏;QuickTime虚拟现实电影;VRML(虚拟现实建模语言)场景;诸如“皇宫”“积极世界”等图形化聊天环境。——作者注
[6]ID software 的游戏产品,一直都走在 3D 显示技术前端。——作者注

文化内容计算机化,导致了新文化形式的涌现,比如电子游戏和虚拟世界。不仅如此,它还重新定义了已经存在的一些文化形式,比如摄影和电影。所以我也散乱地调查了视觉文化中计算机革命的影响。存储和操作图片的媒介由胶卷转变为计算机,这个过程怎样重塑了静态图像与动态图像的内在规律?我们文化中视觉语言的计算机化带来了什么影响?我们由此得到了哪些新的审美可能?

在解答这些问题的过程中,我描绘了艺术、摄影、视频、通信、设计、电影的历史。其中电影是 20 世纪最关键的文化形式。电影的理论与历史是我观察新媒体的绝佳镜子。本书将会探索以下话题:

  • 电影历史和新媒体历史的比较;
  • 数字电影的特征;
  • 多媒体语言和十九世纪电影诞生前文化语言的关系;
  • 屏幕、手持摄像机、蒙太奇在新媒体和电影中运用的对比;
  • 新媒体和先锋电影之间的历史联系。

对照电影历史,本书将会从人性和科学的角度描绘新媒体的理论框架,包括艺术史、文学理论、媒体研究、社会理论、计算机科学等。我研究新媒体的总体方法可以称作“数字唯物主义”。我会从头开始构建新媒体的理论,而不是引用先验的理论。为了发现新的文化逻辑,我仔细探究了计算机硬件和软件的本质,以及在计算机上创造新文化对象所需要的操作。

大部分关于新媒体的著作充满了对未来的预测,本书则专注分析新媒体已经发展的现实。事实上现在新媒体艺术家和设计者的发展方向尚未明确。我希望我关于新媒体的这些理论不仅能帮助人们了解现状,而且而且能够为应用实验确立坐标。例如,“文化界面理论”这一章分析了打印、电影、人机界面这三项文化传统是如何塑造新媒体对象界面的。通过描述这些已经在新媒体中得到运用的传统元素,我分析指出了其他有待运用的元素和元素组合。“组合”一章列举了一批新的蒙太奇手法,为新媒体实验展示了一些新的方向。“数据库”一章中,我指出计算机数据库可以为新媒体叙事提供新的内容组合与审美可能,这是另一个发展方向。

虽然这本书没有预测未来,但是它还是隐性包含了新媒体发展的理论。这是在更大历史视角下观察新媒体的好处。我们开始观察新媒体发展至今的历史轨迹,我们推断这条轨迹今后将怎样延伸。“新媒体原则”一章描述了我眼中新媒体发展历史上最重要的几个趋势:模块化、自动化、可变性、转码性。

当然我们并不是盲目承认这些趋势的。理解塑造新媒体革命的逻辑过程,可以让我们发展出新的新媒体特性。先锋电影制作者在电影已经存在的情况下开发了新的视听叙事手法,与此类似,如今先锋新媒体艺术家的任务就是开创新的计算机媒体语言。如果我们的理论可以揭示现在“主流”语言的构造方法,先锋艺术家就可以更容易地发明创造。

草绘新媒体:组织

本书描绘了新媒体研究领域的一种可能性,希望能够促进新媒体研究(数字化研究)这一新生领域的发展。就像文学理论教材可能以叙事和声音的章节为重点,电影研究教材可能重在讨论摄影和剪辑,本书提出了新媒体理论中新范畴[7]体系的定义和精化。

[7]在哲学中,范畴(希腊文为 κατηγορια)概念被用于对所有存在的最广义的分类。比如说时间,空间,数量,质量,关系等都是范畴。在分类学中,范畴是最高层次的类的统称。它既不同于学术界对于学问按照学科的分门别类,又有别于百科全书式的以自然和人类为中心的对知识的分类,范畴论是着眼于存在的本质区别的哲学分类系统。——译者注

我已经把书分成了若干章,每章介绍一个关键概念或者关键问题。前面章节介绍的概念是后面章节分析的基础构件。我参考了与新媒体相关的各已有领域的教材,例如电影研究、文学理论、艺术历史。

很多电影教材可能从电影技术讲起,以电影流派结尾。本书的套路几乎一样,从新媒体的物质基础讲到它的形式。

术语:语言、对象、表征

我在本书标题中加入了“语言”这个词,但是这并不意味着我们在理解新媒体时需要从语言符号的结构开始。相反,现在大部分关于新媒体和计算机文化的研究都把重点放在社会学、经济学、政治学领域。我用“语言”这个词揭示本书与众不同的重点,即:新媒体新兴的表征习惯、重复出现的设计模式、关键的实现形式等。我也考虑过“美学”“诗性”这两个词,但是最终还是决定采用“语言”。“美学”有很多我不喜欢的对立——例如艺术文化和大众文化、美和丑、有价值和不重要等。“诗性”也承担了一些我不希望有的内涵。基于俄罗斯形式主义者 1910 年代的工作,1960 年代的理论家将“诗学”定义为研究某种特殊艺术形式具体属性的学科,就像叙事文学那样。例如,文学家茨维坦·托多洛夫在他的著作《诗歌导论》中说:

“与对特定作品的解读不同,它(诗性)寻求给意义命名,旨在探寻作品诞生的普遍规律。与心理学、社会学等科学相反,它只在文学自身内部探索规律。所以诗性是一条既‘抽象’又‘内在’的通往文学之路。”[8]

[8] 茨维坦·托多洛夫,《诗歌导引》,译:理查德·霍华德(明尼阿波利斯:明尼苏达大学出版社,1981年)。——作者注

与这种“内在”方式不同,我不认为新媒体的习惯、元素、形式是史上独特的,也不认为孤立地研究它们会很有意义。相反,本书希望能够将新媒体与文化的其他领域建立联系,无论是过去的元素还是现在的元素,列举如下:

  • 其他艺术和媒体的传统:他们的视觉语言和他们组织信息、营造受众体验的策略等;
  • 计算机技术:计算机的物理性质、计算机在现代社会中的使用方式,计算机交互界面的结构、计算机的关键软件应用等;
  • 当代视觉文化:内部组织、图像志、图像学,还有我们文化中多种多样视觉现场的受众体验,例如时尚和广告,超市和艺术品,电视节目和宣传横幅,办公室和电子音乐俱乐部等;
  • 当代信息文化。

“信息文化”这个概念是我发明的,可以和我们已经熟悉的另一个概念相对照——视觉文化。信息文化包括了不同场景和物品中呈现信息的方式——路标,机场和火车站的显示屏,电视机菜单,电视新闻的平面布局,书籍、报纸、杂志的版面设计,银行、旅馆、其他商业场所和休闲场所的室内设计,飞机和汽车的操作界面,计算机操作系统(Windows、Mac OS、UNIX)和软件应用(Word,Excel,PowerPoint,Eudora,Navigator,RealPlayer,Filemaker,Photoshop等)的界面等。与视觉文化相应,信息文化也包括信息组织方式、信息获取方式(影像学的相似概念)和用户与信息对象、信息呈现的交互模式等。

另一个值得一谈的术语是“对象”。整本书中我都使用了“新媒体对象”这一术语,而非“产品”“艺术作品”“交互媒介”或者其他术语。一个新媒体对象可能是数字照片、数字电影、虚拟三维环境、电子游戏、超媒体DVD、超文本网站、万维网等。“对象”这个术语和我试图描述新媒体通用规则的目的相一致,这些规则同样也适用于所有的媒体类型,适用于不同的信息组织形式,适用于所有的信息规模。我用“对象”这个词也是为了强调我对于文化的广泛领域都很关心,而不仅仅是新媒体艺术。其次,“对象”是一个计算机科学和计算机工业中的标准术语。在计算机的面向对象编程语言中,“对象”强调语言的封装模块特性。这些语言包括C++、Java、面向对象数据库、微软Office产品中的对象链接和对象嵌入技术等。这就实现了我的目标:在计算机文化的理论中采用计算机科学的术语和范式。

此外,1920 年代俄罗斯先锋艺术家们也使用了“对象”一词,我希望它也能够包含这一层内涵。俄罗斯建构主义者和生产主义者都把他们的创造叫做“对象”(对象、结构、语言[9]等)而非艺术品。就像建筑领域的包豪斯,先锋艺术家更愿意成为工业设计师、图像设计室、建筑师、服装设计师,而不是成为传统艺术家,像传统艺术家那样为博物馆和私人收藏打造独一无二的艺术品。“对象”更多意味着工业化规模生产,而不是传统艺术家的手工作坊。它也意味着艺术家愿意将合理的劳动组织和工程效能代入他们的艺术创作之中。

[9] 原作中作者列夫·曼诺维奇在这里生造了三个英文单词,来模拟俄语术语的发音,分别是 vesh、construktsia、predmet——译者注

对于新媒体对象,以上所有的内涵都是很有价值的。在新媒体的世界,艺术和设计之间的界限很模糊。一方面,很多艺术家以商业设计为生;另一方面,职业设计师往往通过系统性实验和创立新标准新风格推进新媒体语言的发展。“对象”的第二点内涵,关于工业生产的内涵,也适用于新媒体。很多新媒体工程是大型团队共同推进的(与单人制片人、小团队、经典好莱坞时代的制片体系不同)。很多新媒体对象都销售了逾百万份,例如一些流行的电子游戏和软件应用。它们需要适应花样繁多的硬件软件标准,这样新媒体领域的特征使得它需要大规模的工业生产。[10]

[10]软件标准包括但不限于操作系统(UNIX、Windows、Mac OS等)、文件格式(JPEG、MPEG、DV、QuickTime、RTF、WAV等)、脚本语言(HTML、Javascript等)、编程语言(C++、Java等)、通信协议(TCP-IP等)、人机交互规范(对话框、剪贴板、提示帮助等)、一些不成文的惯例(例如,有十年多图像大小都是固定的640×480像素)。硬件标准包括存储介质格式(极碟、爵士可扩充硬盘、只读光盘、数字光盘)、接口类型(串行接口、通用串行总线、火线),总线架构(外部控制器接口)、随机存储器类型。——作者注
极碟是美国埃美加(Iomega)公司所发明的一种高容量软式磁盘机,使用具有较坚固外壳的特制高容量软碟片,并利用部分硬盘中使用的技术,制成的个人电脑储存装置。爵士可扩充硬盘是美国埃美加(Iomega)公司利用硬盘技术制成的可移除存储设备。通用串行总线即日常生活中俗称的 USB 接口。火线(FireWire)接口是IEEE 1394的别名,是由苹果公司领导的开发联盟开发的一种高速传送接口。外部控制器接口是是一种连接电子计算机主板和外部设备的总线标准。当代计算机主板上的大部分插槽都是外部控制器接口规范插槽。——译者注

最后,也是最重要的,我用“对象”这个词暗示1920年代先锋艺术家们的实验室实验概念。现在,越来越多的艺术家转向新媒体,却没有多少人愿意针对新媒体元素,针对最基本的信息组合、表征、生成策略,展开系统的、实验室级别的研究。而这正是1920年代俄罗斯福库特马斯设计学院和德国公立包豪斯学校的先锋艺术家们所做的研究。他们探索了他们时代的新媒体:摄影、电影、新式打印技术、电话通讯等。现在,发明“可读写光盘”“数字电影”这些新产品的直接诱惑实在太大了,几乎没有人能够抵挡住这样的诱惑,转而专注于寻找镜头、语句、词语、甚至字母在新媒体概念中的等价物,去寻求惊人的发现。

第三个贯穿本书且需要点评的术语是“表征”。近几十年人类文明发展出了不少新生的文化对象,我使用“表征”一词,就是希望能够引入对这些文化对象运作方式的理解,复杂而又细致的理解。新媒体对象是文化对象。所以,任何新媒体对象,无论是网站,电子游戏,还是数字图片,都是在表征或构建一些外物,例如:实实在在的物理对象、其他文档中的历史信息、文化整体或特定社群的范畴体系等。就和其他文化表征一样,新媒体表征也难免有倾向性。它们牺牲其他内容,只描述出物理现实的部分特征。它们在诸多世界观中选择一个,在大量范畴体系中表达其一。对于操作系统和软件应用,它们的软件界面也是表征形式。本书中我会通过陈述这一点进一步论述新媒体表征的倾向性。用特定方式组织数据,新媒体就可以突出某种描述人与世界的模型。例如,目前组织计算机数据的两大常用方案分别是树形目录文件系统(自1984年麦金塔[11]计算机的图形用户界面起)和扁平的超链接网络(1990年代诞生的万维网)。它们采用了根基不同、截然相反的方式表征这个世界。树形目录文件系统认为这个世界遵循逻辑分层的秩序,每个对象都有明确不同的位置。万维网模型认为每个对象都一样重要,每个对象都可以和其他对象相联系。[12]此外,界面也可以凸显某种数据访问方式,与特定艺术作品和媒体技术相联系。例如,1990年代的万维网将网页作为数据组织的基本单元,而Acrobat软件给文本文档提供了视频播放功能。界面起到了旧文化形式和媒体的“表征”作用,强调部分内容,轻视部分内容。

[11]麦金塔电脑(Macintosh),俗称 Mac 机,也称作苹果机或麦金托什机 ,是对苹果 PC 中一系列产品的称谓。首款 Mac 于 1984 年 1 月 24 日发布,是苹果公司继 Lisa 后第二款具备图形界面的 PC 产品。——译者注
[12]首先,目录文件结构并不诞生在 1984 年,在图形界面出现以前,树形文件结构早就广泛存在。在计算机领域中,文件目录结构与超链接网络也不是对立关系。每一个位于目录中的文件都有自己的链接地址,网络中超链接的相对关系也需要依靠目录结构来表征。在计算机工业世界,两者分工合作,各有所长。而且你中有我,我中有你,互相交融,远非对立。译者认为作者在这里对两种数据组织方式有片面的处理。——译者注

我发现,在描述新媒体语言时,“表征”一词的对立意义非常有用。给“表征”选择不同的对立意义,“表征”就能体现出不同的内涵。这些对立意义的介绍分散在本书的各个章节,我总结如下:

  1. 表征——仿真(“屏幕”小节)。这里,“表征”意味着各种屏幕技术应用,例如后文艺复兴绘画、电影、雷达、电视等[13]。我将“屏幕”定义为一个矩形表面,它展现虚拟世界,但同时也是用户物理世界中的一个实际存在,不会完全遮蔽用户的视野。“仿真”则指让用户完全沉浸在虚拟世界中的技术,如巴洛克的耶稣教堂、十九世纪的全景图片、二十世纪的电影院等。
  2. 表征——控制(“文化界面”小节)。这里,我把两种图像对立起来,一者是虚构世界的视觉表征,一者是控制面板(例如,图形界面及其图标、菜单)的细节模拟。控制面板使用户可以操作计算机,这种新型的图像可以称作“界面图像”。表征和控制这一组对立对应着深度和表面的对立。例如,计算机屏幕,在表征情境下是通往虚拟空间的窗口,在控制情境下则是一个扁平的控制面板。
  3. 表征——操作(“遥控”小节)。创造幻觉(时尚、写实油画、西洋镜、军事诱饵、电影蒙太奇、数字合成等)的技术和执行操作的技术存在对立。执行操作的技术可以让用户通过表征(地图、建筑图纸、X射线图、远程监控等)操作真实对象。我把执行操作的图像成为“工具图像”。
  4. 表征——通信(“遥控”小节)。表征技术(胶卷、音频、录像磁带、数字存储格式等)和实时通信技术(电报、电话、电传[14]、电视、远程监控等)构成对立。表征技术可以让人创造传统美学对象,这些对象存在于确定的时间或空间,并且涉及它们之外的事物。现在人与人之间的沟通交流越来越重要,“通信文化”形式一般不产生任何文化对象,新媒体迫使我们重新思考传统上文化和对象的等价关系。[15]
  5. 视觉幻觉艺术——仿真(“幻想”一章的引语)。这里,幻觉艺术包含“屏幕”小节中表征和仿真的双重意义。幻觉艺术结合了传统技术和旨在创造虚拟真实视觉的技术,如视角化绘画、电影、西洋镜等。这里的“仿真”指除视觉表现外,计算机模拟现实其他内容的方法,如物理对象的移动、自然现象中的物体形变(水面、烟雾等),动机、行为、人类的言谈和语言表征等。
  6. 表征——信息(“形式”一章的引语)。新媒体有两个对立的设计目标,一者像传统小说那样,希望用户沉浸在虚拟世界;一者希望给用户提供获取信息的高效渠道(搜索引擎、网站、在线百科等)。

[13]这些设备或艺术品都需要引入屏幕技术。——译者注
[14]电传是一个合成词,是远距离打印交换的缩写形式。电传既具有电话的快速,又具有打字机的准确,尤其是当电文中有数据时,这种优点表现得特别明显。——译者注
[15]古时人们沟通会产生书信等具体的文化对象,这些文化对象往往记载着时间、地点等重要的外部事物信息。但是现在,如果没有刻意地录音、存储,大量信息就耗散在电波和光纤里,不形成文化对象,也不指涉外部。——作者注

导语

本文力求在万字篇幅内尽可能清晰地介绍计算理论的基本概念和最新发展。

普通科学读物总是逻辑清晰环环相扣,但是这实在把读者累坏了。本文作为心疼读者的二逼科学读物,目标是希望读者在看不懂第一章的情况下仍有可能把第二章看下去。对于涉及到的新兴专业术语,作者将做出尝试性的汉语翻译,用汉语的语法、汉语的风格、汉语的词汇展现全文。

可计算性问题

现实生活中有很多计算类的问题,考试要计算成绩,购物要计算价格,与佳人约会要算好时间,出门旅行要算好乘车方案。计算的结果不局限于数字,也可以是方案,可以是图像,可以是子弹穿过木块的运动轨迹,也可以是组成新款计算机的电路设计。只要一份答案可以用语言描述,它就可能是某个计算过程的结果。

可是世界上并不是所有问题都能算出结果。姑娘的头发有多少根,这个问题很难,但是交给机器做,一根一根数,数一根拔一根,总是能数完的。这个问题就可计算。但是姑娘明天心情如何,这个问题就根本没办法计算了。事实上就连她们自己也弄不清楚。

那么,什么问题是可计算的?什么问题是不可计算的?我们能不能在数学上给“可计算”下一个精确定义,然后用数学手段研究万事万物的可计算性?

历史

这个问题的源头早在17世纪就被提出来了。欧洲大陆近现代数学的共同导师莱布尼茨,在发明了相当完善的微积分体系后,马不停蹄地试图再发明出一套数学机制来判断任何逻辑陈述的真假。但是这个问题的难度已经远远超出了莱布尼茨的时代,首先,莱布尼茨缺乏数学工具去描述逻辑陈述本身;其次,也没有成熟的逻辑知识去帮助他理解逻辑。但是他已经隐隐地感受到,有必要创造出一种“形式语言”来描述问题。

世界上最后一个通晓所有数学领域的数学家希尔伯特,用他的天才智慧和完美主义创造了完善的希尔伯特公理体系,构建了完整的逻辑规则,在一阶逻辑上找到了既可靠又完备的演绎系统。1928年,在逻辑学基础上,他正式提出了这个问题,数学史上大名鼎鼎的判定问题,德语Entscheidungsproblem,英语Decision Problem:我们能不能找到一种算法来判定一切一阶逻辑陈述的真假?

“算法”“一阶逻辑”这样的字眼实在晦涩费解,事实上算法我们就可以理解为一种可行的方法或机制,而一阶逻辑是数学中公理系统的标准形式逻辑,大部分判断句都可以用一阶逻辑的陈述来表达。而那种经常会产生悖论的“整数和偶数一样多”这类蕴含着“无穷大”概念的判断,则不在一阶逻辑范畴之内。这些给数学和逻辑添麻烦的魂淡问题,我们今天就先不理会了。

所以我们可以用更形象的语言来描述这个问题,这个问题是在问我们,我们能不能造出来一个黑箱子,做对这世上一切判断题?

咦?这个问题看起来强度有点弱啊,我们刚才是可以数女生头发数目的,我们是可以做解答题计算题的,可是这个判定问题只对判断题有要求。

没关系,很多计算题也可以转化成判断题。我们只要不断地向黑箱子问:“她有1根头发吗?”“她有2根头发吗?”……只要你寿命够长能把问题问完,总有一天,你会得到正确答案。一上来就直接考虑计算题,对我们而言太难了,所以我们先从判断题开始吧。

形式语言与图灵机

语言

莱布尼茨需要一种工具来描述问题。描述问题,当然需要语言。什么语言呢?中文?Engish?二进制数码1111111111?printf(“C++”)?吙煋呅?都不是。下面我要隆重推出高端大气上档次的形式语言,一大波定义即将袭来,大家耐耐性子,文科生也能看懂的~

直观上说,语言都是字符串组成的,这里的语言也不例外。我们假设字母表Σ为任意有限集合,\(\varepsilon\)表示空串,记\(\Sigma_0\)为\({\varepsilon}\),\(\Sigma^* = \cup_i(\Sigma_i)\)。

定义:语言\(L\)为\(\Sigma^*\)的任意子集。

举个例子,假设字母表\(\Sigma\) = \({S, B}\),那么\(\Sigma^2 = {SB, SS, BS, BB}\),把所有的\(Σ_i\)并起来,就得到\(\Sigma^ = {\varepsilon, S, B, SB, SS, BS, BB, SSB, \dots}\)。这样所有有限长的SB串就都包括在\(\Sigma^\)里了。我们取\(\Sigma^*\)的任何一个子集,就都构成一个语言。

全\(S\)串,全\(B\)串,只有一个\(S\)的串,\(S\)和\(B\)一样多的串,……他们都是字母表\(\Sigma\)上的语言。给定任何一个字母表\(\Sigma\)上的字符串\(w\),给定一个\(\Sigma\)上的语言\(L\),判断\(w\)是否属于\(L\),也就等价于做一道判断题。

图灵机

阿兰·图灵,英国杰出的同性恋数学家,二战时德军密码的破译者,计算机科学的宗师,在1936年5月发表了一篇划时代的论文《论可计算数及其在判定问题中的应用》。判定问题就是我们上文提到的希尔伯特判定问题;可计算数,就是我们上文提到的可以计算出来的答案。图灵为了解决这个问题,发明出了一台惊世骇俗的机器模型,说只要是这台机器能计算的,就是可计算的;这台机器能判定的,就是可判定的。此机一出,判定问题彻底终结,江湖人称“图灵机”。

说到这图灵机啊,结构十分简单。一条长长的纸带,一个读写头,读写头指向纸带上的一个格子,可以在纸带上自由地左右移动,这就没了,和我们这一代人小时候常见的磁带机差不多。当然了,也有区别。纸带是无限长,划分成无限多个格子,每个格子里可以填一个字符。这里也可以填\(\varepsilon\),也就是啥也不写,空在那。读写头有\(n + 3\)个状态\(Q = {q_0, \dots, q_n, q_a, q_r}\),初始时,读写头的状态是\(q_0\),位于纸带上某个字符\(x\)之上,读写头会根据\(q_0\)和\(x\)这两条信息,决定做出三件事:

  1. 把x改写成字符y
  2. 向左或者右移动一格
  3. 把自己的状态切换为某个\(q \in Q\)

这种决定不是读写头一拍脑袋想的,而是我们事先设计好的。我们事先就决定好了一台图灵机的字母表\(\Sigma\)、状态集\(Q\)、 读写头在每个\(q, x\)的情况下做出什么动作,机器在达到哪些状态的时候停下。

好了,一台图灵机的结构就这么简单。让我们来看几个例子吧。

识别与判定

我们假设图灵机有两个停止状态\(q_a, q_j\),当读写头切换到这些状态的时候,图灵机就停止了。如果图灵机停在\(q_a\),我们称它接受(accept)了输入串;如果停在\(q_r\),我们称它拒绝(reject)了输入串。

定义:如果存在一台图灵机可以接受语言\(L\)中的所有串,我们称\(L\)是可识别的。

定义:如果存在一台图灵机可以接受\(L\)中的所有串并拒绝\(\Sigma\backslash L\)中的所有串,我们称\(L\)是可判定的。

我们现在把\(\Sigma\)都设置成\({0, 1}\),也就是二进制码。设\(L\)为所有全0串的集合,那么我们很容易发现\(L\)是可判定的。

证明:构造一个图灵机\(M\),它有3个状态\(q_0\), \(q_a\), \(q_r\)。再设置读写头的工作函数\(\delta\),使得\(\delta(q_0, 0) = (q_0, 0, 右),\delta(q0, 1) = (q_r, 0, 右), \delta(q_0, \varepsilon) = (q_a, 0, 右)\)。这个图灵机就可以判定\(L\)。

这个例子太简单,大家可以试试看怎么构造图灵机判定所有回文串的集合\(L’\)。

此外,这个世界上还有很多奇葩问题——或者说语言——是只能识别不能判定的。比如说大名鼎鼎地停机问题:给定一台图灵机和一个输入串,让图灵机能在这个输入串上运行,请问这台图灵机能停下吗?

我们可以很容易地识别出能停下的情况,只要模拟这台图灵机的运行情况就可以了,一旦停下就对外声称这个图灵机可以在这个输入下停止;但是如果不停呢?对不起,数学家已经证明,没法识别。

理论、算法、应用

我们现在手头已经有了语言和图灵机这两大工具,已经可以开始建设计算机科学的理论大厦了。在这之前,我认为非常有必要提一提理论的意义。

昨天小师妹段萌软就问,理论是神马?理论可以吃吗?

很遗憾,大部分第一流的理论研究不仅不能吃,甚至都是没有“用”的。它离我们的现实生活实在太遥远,写不出百度也造不出 QQ,不能让我们的选课快上一秒,也不会让情侣间少丢几条短信情话。

理论研究的问题往往是,“如果明天的天气可以预测,那么女孩儿的心情也可以预测”这种命题?这个问题如果证明了,就是理论界的重大突破,我们只要能预测天气,就能猜对女孩儿心思了。多么美妙啊!可是,现实中大家既不能预测天气也不能预测女孩儿的心思,所以这个命题不管被证明还是被推翻,对于我们的现实生活一点帮助都没有。大家和妹子交往,还是要看天吃饭。

哎,我把理论说得也太不堪。事实上理论不仅对于现实有深远指导价值,其本身蕴含的智慧更是人类精神文明的伟大见证。

计算机科学的宏伟格局,理论、算法、应用,三位一体,缺一不可。

譬如我们想为广大懒助教提供一个自动批改试卷选择题的程序,这一程序就是应用。为了做出这个应用,我们需要设计一个识别正确答案的算法,而理论告诉我们这个问题是可判定的,我们一定能找出一个算法解决问题。

应用有时会驱动理论的发展,譬如,如果助教希望这个程序还能够批阅解答题,那么我们就需要为解答题设计新的算法,这可太难了,我们的程序得能理解语义才行。能否让程序去理解自然语言的语义,这就是一个理论问题了。只有理论解决,我们才能够提出切实可行的算法,来实现这一应用。

相反,理论的进步也可以指导应用的发展。比如,理论告诉我们,一个问题是不可解的,那我们设计算法时就可以避开这个地雷。又如,理论告诉我们,在二维平面上随机游走会无限次经过原点,那么我们在设计算法的时候,就可以设计回到原点后程序的种种行为,不用担心无法返回。

诚然,理论是一切方法和应用的基石,就像物理理论是电灯、电脑、汽车、楼房的基石一样。没有理论支持,我们也可能造出电灯泡。但有了理论支持,我们就能知道电灯的原理,就可以研发各种新款电灯。另一方面,理论还能证明使用电灯既不会导致核爆也不会导致怀孕,这样大家用起来才安心,才能确保在重要场合使用电灯不会带来一些难以预料的副作用。

然而,大部分理论就像我前文所说,是基本上没用的。理论就像法拉第口中的婴儿,只有长大了才能彰显出独特的价值。

计算的时间复杂度

P vs NP

任何计算过程都需要耗费时间与空间。对于图灵机而言,读写头移动的次数就是消耗的时间,读写头走过的纸带格子数就是占用的空间。如果输入串的长度为\(n\),图灵机的时间消耗不大于\(f(n)\),我们称这个语言可以在\(DTIME(f(n))\)时间内得到判定。如果\(f(n)\)是关于\(n\)的线性函数,我们称该语言可以在线性时间内得到判定;如果\(f(n)\)是关于\(n\)的多项式函数,我们称该语言可以在多项式时间内得到判定;如果\(f(n)\)是关于\(n\)的指数函数,我们称……后面就不用我多说了吧。

对于那些可以在多项式时间内得到判定的语言,他们组成的集合就是\(P\),单词多项式polynomial的首字母,大名鼎鼎的\(P\)。

\(P\)是语言的集合,这些语言的判定问题我们俗称\(P\)问题。

至于那些可以在多项式时间内得到验证的语言,它们的集合就叫做\(NP\)。

什么叫验证?什么叫\(NP\)?直接说太麻烦,让我们看个例子吧。

问题:OrangeCLK 期末论文写不完了,想找人代写。可是这事儿可绝对不能让老师知道,所以一定要找他的死党。OrangeCLK 是个 geek,他居然用数字来表示他和朋友间的好感度。他说了,只有好感度超过 100 的朋友才算死党,现在给你一份包含陈力坤所有朋友好感度信息的数据表格\(T\),问他能找到\(k\)个朋友帮他代写论文吗?

这是一道不折不扣的判断题,而且它在多项式时间内就能做完,图灵机只要一一扫过那些数据,数数有没有\(k\)个大于 100 的数据就可以了。图灵机可以很聪明地数数,它现在纸带某个空白的地方写上\(k\),并且每扫描一个数据就擦除掉,每发现一个满足要求的数据就跑到写\(k\)的地方给\(k\)减一。如果\(k\)能减到 0,图灵机停止运行,OrangeCLK 论文得救,如果图灵机看遍所有数据,原先写\(k\)的地方还是个正数,那 OrangeCLK 就只能挂科了。好,这里给读者留个题目,图灵机怎么做加减法呢?大家有兴趣就自己动手设计个\(\delta\)函数试试吧。

我们看到,给定输入\(w\),存在一台图灵机先验证\(w\)是不是\(\langle T,k\rangle\)这样的格式,然后执行上述算法,就可以在关于\(|w|\)的多项式时间内判断问题的是或否。所以\(L = {w \in \Sigma^* : w = \langle T, k \rangle \land 能找到 k 个好感度达标的人}\) 属于 P。

问题:OrangeCLK 提高了对代写人选的要求,他们不仅都要和 OrangeCLK 关系好,彼此好感度也要超过 100 才行,否则可能会内讧。还是给出好感数据表\(T\)和需要人数\(k\),问能不能找到这样的\(k\)个人?

先来浇一盆冷水,傻×的 OrangeCLK 死活也找不到这个问题的多项式解法。于是他就捉急了,因为他的智商只能做多项式时间的运算。这时候有一位大神告诉他,咦,你挑这\(k\)个人就 OK 啦。于是 OrangeCLK 开开心心地把大神给他的\(k\)人方案一拿,把\(\frac{(k + 1)^2}{2}\)对好感度数据一查,果真,包括他本人在内的这\(k + 1\)个人彼此好感度都超过 100,我们看到\(\frac{(k + 1)^2}{2}\)这个数字显然是多项式的。大神给的\(k\)人方案,就好比是一串验证辅助串\(v\),有了这样一串验证辅助串\(v\),由于图灵机对每一个数字大小判断的元操作也是多项式级别,我们就能构造出一台图灵机,基于输入\(\langle w, v \rangle\),在多项式时间内验证\(w\)是否属于\(L\)。

所有可以借助验证串在多项式时间内验证的语言,组成了集合\(NP\),对应的问题叫做\(NP\)问题。

\(NP\)中的\(N\)是 nondeterministic 的意思,意指不确定机。不确定机和上文我描述的图灵机有一点区别,它表头的转换机制不是确定的,看到一组\((q, x)\),它可能有几个不同的操作方式,而且每一步都有这样相同多样的操作方式,最后只要有一种碰上停止状态\(q_a)或(q_r\),整个程序就告结束。\(NP\)也可以理解为,所有可以被不确定机在多项式时间内判定的语言集合。和验证版本的定义等价。

我们很在乎多项式,因为多项式是我们可以承受的计算时间。多项式之上是指数,指数级的时间复杂度是几乎没有实际计算价值的。举个例子,如果一个问题对于长度为\(n\)的输入串需要运行\(10^n\)步,那么对于长度为 80 的串,这台图灵机就要跑\(10^{80}\)步,\(10^{80}\),大概是全宇宙原子总数那么多,宇宙的寿命还不到\(10^{17}\)秒。所以,多项式才意味着可计算,超出多项式,我们就当不会做。

很显然,\(P\)是\(NP\)的子集,那么,\(P\)和\(NP\)相等吗?存在一个语言属于\(NP\)却不属于\(P\)吗?

这就是世界闻名的\(P=NP\)问题,是21世纪数学最重要的十大问题之一,五大问题之一,三大问题之一,一大问题之一。

太重要了,可也太难了,我们既找不到方法在多项式时间内就能判定 OrangeCLK 能否找齐代写论文的人,也不能证明这样的方法不存在。天下所有的\(NP\)问题,都像这幽灵一般让人捉摸不透。

NPC,问题归约

\(NPC\)?哈哈,这可不是打游戏的时候遇到的 NPC,它的全名叫做 NP-Complete,中文雅号\(NP\)完全。和\(P,NP\)一样,也是一个语言的集合。

我们都聊到\(NPC\)了,OrangeCLK 还在纠结找人代写论文的严肃问题。机智の OrangeCLK 发现,他面临的问题其实可以转化。如果把每个人都看成一个点,两人之间的好感度如果超过 100 就连一条边,如此我们就得到了一张数学意义上的图。原问题就转化为,能不能在这张图\(G\)中找到一个\(k + 1\)完全子图?看到没有,一个偷鸡摸狗的作弊问题瞬间被转化成了一个高端大气上档次的数学图论问题。数学家们对这个问题可是颇有兴趣,可惜,要找这个问题的多项式解法?他们也不会做。记得我在探讨理论、算法、应用三者之间关系的时候怎么说来着?理论大部分时候都是没用的,它的“精髓”就是把一个大家都不会的问题转化为另一个大家都不会的问题。我们打小从数学书上就学着要化未知为已知,可是人生总是如此的艰难,现实中哪有那么多已知呢?在计算理论研究中,真的勇士,敢于面对惨淡的现实,敢于面对凶残的无知。科学家不断开拓新领域,做着化未知为未知的转化,这种工作,叫问题归约,同时也是在给问题分类。同一类的问题,具有相同的时空性质,整个类的问题都休戚与共同生共死。于是,一个问题得解或者是得证无解,就会推进许多领域大量问题的解决。不管问题我们现在会不会做,大家都致力于打通问题之间的任督二脉,这样在问题的茫茫荒原中,将来只要有一个旷古烁今的灵光一现,大批量的问题都会瞬间得到解决。敢于在一片未知之中闪转腾挪创造科学结构,需要多么大的胆略与魄力!这就是人类伟大的远见卓识壮志雄心。

我们看到,代写论文问题被归约到了\(k\)完全子图问题。只要我们能在多项式时间内做出完全子图问题,我们也一定能在多项式时间内做出代写论文问题,因为这个归约过程本身的计算也是可以在多项式时间内完成的。

下面我要公布一个让你合不拢下巴的事实:所有\(NP\)问题都可以归约为\(k\)完全子图问题。

啥?没震惊?那我换个说法,只要我们在多项式时间内解决了\(k\)完全子图问题,天下所有的\(NP\)问题就都能在多项式时间内解决。没错,是所有!这样\(P\)和\(NP\)就能画上一个大大的等号,21世纪最大数学难题就可以告破。

原来\(k\)完全子图问题如此特别,我们有必要引进一个新的类型。刚才说了,计算理论的一项重要工作就是给问题分类。于是\(NPC\)应运而生,\(NPC\)中的任何一个问题得到多项式解决,\(P\)就和\(NP\)相等了。

科学家们已经发现了一大堆\(NPC\)问题,显然,它们非常争气,都没有被人类解决。

NP 难

这货英文名叫\(NP-Hard\),我这篇文章,有一半动机都是为了这个坑货而写。

这玩意儿坑在哪儿呢?学术界到现在对于\(NP-Hard\)居然没有一个统一的定义!各个山头的大佬们众说纷纭各持己见。我今天就来努力梳理一下。

前面讲到我们只讨论判断题,判定问题。现在呢,我们可以考虑解答题了,专业叫法,搜索问题。

图灵机做判断题,无非是停机,并且停在一个接受/拒绝的状态上,根据停机状态来判定答案。而搜索问题要怎么应对呢?这需要图灵机在纸带上写出答案。输入“2+2”,要能输出“4”。简而言之,除了是/非类型的问题,就是搜索问题,意指在茫茫大海中寻找答案。

既然名字叫\(NP\)难,不说比\(NP\)还难,起码不能比\(NP\)容易。怎么度量难易呢?可以用问题归约啊,如果A解决了,B就也可以解决,我们是不是说B不会比A难?换言之,A 至少和 B 一样难。所以\(NP\)难是这么定义的:至少和\(NP\)中最难的问题——\(NPC\)问题——一样难。如果一个\(NPC\)问题可以在多项式时间内归约为另一个问题\(H\),那么\(H\)就属于\(NP\)难。如果问题\(H\)能在多项式内解决,则\(NPC\)中的某个问题也能解决,进而所有\(NP\)问题都能够在多项式内解决。

乍一看和\(NPC\)挺像,区别就在于问题类型。\(NPC\)只包括判定问题,\(NP\)难可以包括搜索问题。有一些学派认为\(NP\)难包括普通的判定问题和搜索问题;有一些学派认为\(NP\)难还应该包括不可判定问题比如停机问题;还有一些学派认为\(NP\)难不应该包括判定问题只能讨论搜索问题。这些分类方法都有合理之处,最终谁将胜出,还看历史选择。

但是,总有那么些问题是大家公认属于\(NP\)难的,比如最大完全子图问题:给定一个图\(G\),求出它最大完全子图中有多少个节点。很显然,这是一个搜索问题,而且一旦这个问题有多项式解,\(k\)完全子图也就不在话下了,OrangeCLK 的论文也就得救了。

这里宕开一笔,年幼时看科学,总觉得科学与艺术不同。艺术是审美和表达,充满了主观的想象与个人的判断;而科学是客观和真理,奠基于严密的逻辑和重复的实验。年岁渐长,见识益多,渐渐觉得艺术有十分客观之处,科学也有十分主观之处。审美是有一定普适标准的,音乐、美术、文学、戏剧,美好的作品总是蕴含着跨越种族跨越国界的共同感动。科学也根本不客观,科学的理论到底是建立在条条假设上的逻辑推导和计算演绎,不同人观念不同,持有的先验假设不同,构建出的理论体系也就不一样。相信哪个理论,选择哪个理论,是一件很主观的事,也是一件随着历史流变的事。艺术感动人心,科学可以证伪。这是二者在我心中最核心的价值。

计算理论的发展

刚才探讨的只是计算理论的基石,计算理论主要包括包括形式语言自动机图灵机、可计算性、计算复杂度三个部分。广义说来,算法设计、计算经济学、计算生物学、机器学习理论等都属于理论范畴。刚才我们探讨了计算复杂度的时间维度,事实上也有空间复杂度的相关研究,类似于时间,我们有(PSPACE),(LOGSPACE)(简称L)等复杂类。

除了图灵机外,另一个常用的计算模型是电路,研究电路的复杂性很多时候比图灵机方便实用,这也是研究的重大方向。

姚期智教授提出了通信复杂性这个领域,描述交换信息、多机器共同运算的复杂性。

现实生活中由于很多问题得不到完美的解决,人们创造性地发明了很多近似算法和随机算法来解决问题。这些算法不一定能得到最优解,但是离最优解差得不远。那么为了度量算法解和最优解的差距,为了度量得出正确解的概率,为了给这些算法一个理论基石,关于近似算法和随机算法那的理论研究也就顺理成章了。

除了电路、通信、近似、随机,广大理论计算机科学研究者还在努力开拓新的领域,把问题归约到越来越遥远的地方。虽然大部分难题都尚未取得进展,但是已经阐发出很多实用算法,对我们的世界改变良多。

量子计算理论也有不错的发展,取得了一系列诸如\(QIP = IP = PSPACE\)这样的重要结果,全球各大高校和公司也都在加紧制造量子计算机进行量子计算的实验。清华大学交叉信息院量子信息中心(CQI)在这一领域卓有建树,部分方向领跑全球。

就我个人看来,物理理论也好,计算理论也好,都基于数学但是有超出数学的部分。给全所有定理,数学也无法预测复杂系统的运动情况;给定所有运算规则和其实状态,数学也未必能预测某些问题的计算结果。计算领域和物理领域一样,有一些数学无法解释预测的现象。很多数学家不相信的东西,我们可以选择去相信、去实验。在数学力所不及的地方架起计算理论的新结构,发现计算的规律,是一件多么具有挑战性的事啊!

鸣谢

  • 感谢 John Steinberger 的 Brutal and Swift Introduction to Computer Science课程。
  • 感谢Michael Sipser的名著Introduction to the Theory of Computation。
  • 感谢课程指导老师王跃宣。
  • 感谢与我讨论NP-Hard定义的寿鹤鸣。
  • 感谢段萌软提出她对理论的看法。
  • 感谢读者!