epilog.tex

% vim: ts=8 sts=8 sw=4 et tw=75
\chapter{后记}
\label{chap:epilog}
\marginpar{181}

能看到这里, 说明读者在某种程度上已经是一个熟练的 awk 用户了, 至少不再是
一个笨拙的初学者. 当你在学习书中的示例程序时, 以及自己写程序的过程中, 
可能想知道 awk 为什么会是现在这个样子, 是否还有需要改进的地方.

本章的第一部分先讲一些历史故事, 然后讨论一下作为编程语言使用时, awk 有
哪些优点和缺点. 第二部分探讨 awk 程序的性能, 另外, 如果某个问题过于庞大,
以致于无法用一个单独的程序解决时, 文章也提供了一些对问题进行重新规划
的方法.

\section{作为语言的 AWK}
\label{sec:awk_as_a_language}

关于 awk 的工作开始于 1977 年. 在那时候, 搜索文件的 Unix 程序
(\texttt{grep} 和 \texttt{sed}) 只支持正则表达式模式, 并且唯一能做的操作
只有替换和打印一整行数据, 还不存在字段和非数值操作. 我们当时的目标是
开发一款模式识别语言, 该语言支持字段, 包括用模式匹配字段, 以及用动作
操作字段. 最初, 我们只能想用它转换数据, 验证程序的输入, 通过处理
输出数据来生成报表, 或对它们重新编排, 以此作为其他程序的输入.

1977 年的 awk 只有很少的内建变量和预定义函数, 当时只是用它写一些很简短
的程序, 就像第 \ref{chap:an_awk_tutorial} 章中出现的那些小程序. 后来,
我们写了一个小教程, 来指导新同事如何使用 awk. 正则表达式的表示法
来源于 \texttt{lex} 和 \texttt{egrep}, 其他的表达式和语句则来源于 C
语言.

我们希望程序能够尽量得简洁, 最好只有一两行, 这样就能够快速地输入并执行,
    默认操作都是为了向这个方向努力, 具体来说, 使用空格
作为默认的字段分隔符, 隐式地初始化, 变量的无类型声明, 等等, 这些设计
选择都使得 单行程序变成可能. 作为作者, 我们非常清楚地 ``知道'' awk
将会被如何地使用, 所以我们通常只写单行程序.

\marginpar{182}
Awk 的快速传播强有力地推动了语言的发展. 把 awk 作为一门通用编程语言使用,
而且能够这么快速地流行起来, 我们都感到非常的惊喜, 当看到一个无法在
一页内显示完毕的 awk 程序时, 我们的第一反应是震惊和惊异. 之所以会出现这种
情况是因为许多人在使用计算机时, 仅限于 shell (命令行语言) 和 awk, 而不
是使用一门 ``真正'' 的编程语言来开发程序 --- 他们经常过度伸展所喜爱
的工具.

为变量的值同时维护两种表示形式: 字符串与数值, 根据上下文选择合适的形式
--- 这只是一个实验性设计, 目的是为了尽可能地使用同一套运算符集合写出
简短的程序, 在字符串与数值的界限很模糊的情况下, 程序也要能正确地工作.
最终目标完成地很好, 但偶尔也会因为粗心而得到意料之外的运行结果. 第 
\ref{chap:the_awk_language} 章介绍的规则可以用来解决界限模糊的情况, 它
们都来源于用户的使用经验.

关联数组的灵感来源于 SNOBOL4 表格 (虽然它们不具备 SNOBOL4 表格的通用性).
诞生 awk 的机器内存很小, 而且速度很慢, 正是这个环境造就了数组现在的性质.
把下标类型限制为字符串是其中一种表现, 另外的限制还包括单维数组 (虽然套了
一层语法外衣, 但本质上还是一维数组). 一个更加通用的实现应该支持多维数组,
至少支持数组元素可以是另外一个数组.

Awk 的主要特性在 1985 年被加入进来, 主要是为了满足用户需求. 添加的
特性包括动态正则表达式, 新的内建变量与内建函数, 多输入流, 以及最重要的用
户自定义函数.

\texttt{match}, 动态正则表达式和新的字符串替换函数提供了非常有用的功能,
而且对用户来说, 只是稍微增加了一点复杂度.

在 \texttt{getline} 被引入之前, 输入数据的唯一种类是 \patact 语句所隐含
着的隐式输入循环. 这个限制条件确实太强了. 在原来的 awk 版本中, 对于具有
多个输入数据源的程序 (比如格式信函生成程序) 来说, 必须通过设置一个标志变量
(或其他类似的技巧) 来读取数据源. 而在新版的 awk 中, 多个输入数据可以在
\texttt{BEGIN} 部分, 用 \texttt{getline} 读取. 另一方面, \texttt{getline}
是过载的, 它的语法和其他表达式相比并不一致. 其中一个问题是 \texttt{getline}
需要返回它所读取到的数据, 但同时也会返回表示成功或失败的返回值.

用户自定义函数的实现是一个折中方案, 从 awk 的最初设计开始, 出现了许多
困难. 我们并不打算在语言中加入声明, 这个设计造成的一个结果是声明局部
变量的特殊方法 --- 把局部变量写到参数列表中. 这种做法不仅看起来很陌生,
而且会让大型程序更容易出错. 另外, 缺少显式的字符串拼接运算符可以让程序
更加简短, 但这同时也要求在调用函数时, 必须在函数名之后紧跟上左括号. 不
管怎么说, 新的特性使得用 awk 编写大型程序变得更加容易.
\marginpar{183}

\section{性能}
\label{sec:performance}
在某种程度上, awk 是很有吸引力的 --- 通常情况下, 用它编写你所需要的程序
非常容易, 而且在面对适当规模的数据时, 处理起来也足够快, 特别是在程序本身
也会变化的情况下.

然而, 当处理的数据规模越来越大时, awk 程序就会越来越慢. 从常理上讲, 这
种现象是很正常的, 但是等待结果的过程常常使人无法忍受. 解决这种问题
的办法都比较复杂, 但是本节提出的一些建议或许能对你产生一些帮助.

当程序的运行时间过长时, 除了忍耐, 可以试着从其他几个方面入手. 首先, 让
程序运行得更快是可能的 --- 或者利用更好的算法, 或者是把频繁执行的操作,
用等价的, 但是更轻量的操作替换掉. 在第
\ref{chap:experiments_with_algorithms} 章读者已经见到了一个优秀的算法能够
产生的巨大作用 --- 即使是在数据规模只有适度增加的情况下, 线性算法和平方
算法之间也会产生巨大的差距. 然后, 你可以限制 awk 程序的功能, 而使用其
他更快速的程序和 awk 配合. 最后, 你也可以用其他编程语言重写程序.

在着手提高程序的性能之前, 你必须知道程序的时间都花在了哪里. 即使是在 
每种操作和底层硬件非常接近的编程语言中, 人们对时间开销的分布所作出的估计
也会非常不可靠. 在 awk 中, 这些估计会显得更加狡猾, 因为其中许多操作和
传统的机器操作并不对应, 这些操作包括模式匹配, 字段分割, 字符串拼接和
替换. 在不同的机器上, awk 所执行的用于实现这些操作的指令也会不同, 因此
awk 程序中相关操作的开销也就不同.

Awk 并没有内建的计时工具, 因此在本地环境中, 哪些操作属于高开销, 哪些操 
作属于低开销 --- 完全取决于用户怎么理解. 为了分辨出高开销和低开销操作,
最简单的办法就是制作一份不同构造之间的差异度量. 例如, 读取一行数据或
递增一个变量的值需要多长时间? 我们在多种不同的计算机平台上都做了测量 ---
从 PC 一直到大型机. 用一个包含 10,000 行 (500,000 个字符) 的文件作为
输入数据, 运行 3 个程序, 同时和 Unix 命令 \texttt{wc} 作对比. 测试结果
如下:
\begin{center}
\begin{tabular}{l|c|c|c|c|c}
    \hline
    \hline
    \multicolumn{1}{c|}{程序} & \makecell{AT\&T \\ 6300+} &
    \makecell{DEC VAX \\ 11-750} &
    \makecell{AT\&T \\ 3B2/600} & \makecell{SUN-3} &
    \makecell{DEC VAX \\ 8550} \\
    \hline
    \texttt{END \{ print NR \}} & 30 & 17.4 & 5.9 & 4.6 & 1.6 \\
    \texttt{\{n++\}; END \{print n\}} & 45 & 24.4 & 8.4 & 6.5 & 2.4 \\
    \texttt{\{ i = NF \}} & 59 & 34.8 & 12.5 & 9.3 & 3.3 \\
    \texttt{wc} 命令 & 30 & 8.2 & 2.9 & 3.3 & 1.0 \\
    \hline
\end{tabular}
\end{center}
第 1 个程序在 DEV VAX 8550 中运行了 1.6 秒, 也就是说读取一行数据平均
消耗 0.16 微秒. 第 2 个程序表明在读取数据的同时, 递增变量需要额外消耗 
0.08 微秒. 第 3 个程序表明把输入行切分成字段需要 0.33 微秒. 作为对比,
\marginpar{184}
用 C 程序 (在这里是 Unix 命令 \texttt{wc}) 对 10,000 行数据进行计数
需要 1 秒钟的时间, 也就是每行 0.1 微秒.

其他类似的测量表明字符串比较操作, 例如 \verb'$1=="xxx"' 所花费的时间,
和正则表达式匹配 \verb'$1~/xxx/' 大致相同. 正则表达式匹配的时间开销
基本上独立于表达式的复杂程度, 但是当一个复合比较表达式变得越来越复杂时,
它的时间开销也会越来越高. 动态正则表达式的开销可以变得很高, 因为它
可能需要为每一个测试重新构造识别对象.

拼接多个字符串的代价比较昂贵:
\begin{awkcode}
    print $1 " " $2 " " $3 " " $4 " " $5
\end{awkcode}
所花费的时间大概是
\begin{awkcode}
    print $1, $2, $3, $4, $5
\end{awkcode}
的 2 倍.

我们在前面说过, 数组的行为比较复杂. 只要数组中的元素不太多, 则访问一个元素
的时间开销就是一定的. 在这之后, 随着元素个数的增加, 时间开销大致按照线性
增长. 如果元素个数非常多, 这时候程序的性能也会受到操作系统的影响, 因为操作
系统需要分配内存来存放变量. 因此, 相对于小数组, 在大数组中访问一个元素
需要付出更高的代价. 如果你想在数组中存放一个大文件, 那就必须牢记这些.

第 2 个手段是重新构造计算过程, 使得其中一些工作可以通过其他程序完成.
例如在整本书中, 为了避免自己写一个排序用的 awk 程序, 我们用了多次
\texttt{sort} 命令. 如果你需要从一个很大的文件中分离出某些数据, 可以用
\texttt{grep} 或 \texttt{egrep} 搜索数据, 然后再交由 awk 处理.
如果你需要做大量的替换操作 (比如第 \ref{chap:processing_words} 章的交
叉引用程序), 那么可以选择一种流式编辑器 (比如 \texttt{sed}) 来完成这部分
工作. 简单来说, 就是把一个大任务切分成多个小任务, 然后再针对每个小任务
选择一个最合适的工具处理.

最后一个办法是用其他编程语言重写程序. 基本原则是把 awk 中比较有用的内建
特性用子例程替换掉, 除此之外, 尽量让新程序和原程序在结构上保持一致.
不要试图完全模仿 awk 的工作方式, 只要能解决问题就足够了.
比较有用的练习是写一个小型函数库, 函数库提供了字段分割, 关联数组,
和正则表达式匹配, 在某些不支持动态字符串的语言中 (比如 C 语言), 你可能
还需要一些能够方便地分配和释放字符串的子例程. 有了这些库函数, 把 awk 
程序转换成其他更快的程序就方便多了.

通过模式匹配, 字段分割, 关联数组等内建特性, awk 把其他传统语言很难完
成的工作都简单化了. 利用这些特性, awk 程序虽然编写起来比较方便, 但是和%
\marginpar{185}%
认真编写过的等价的 C 程序相比, 在效率上会差一点. 一般来说, 效率并不会
成为什么大问题, 所以 awk 既方便使用, 运行起来也足够快.

当 awk 的效率成为一个问题时, 就有必要测量一下程序中各个部分的运行时间, 看
看时间都花在了哪里. 虽然在不同的机器中, 相关操作的开销都会有所不同,
但是测量技术可以应用在任何一台机器中. 最后, 虽然使用低级语言编写程序
比较麻烦, 但是也要注意理解程序与时间, 否则的话, 新程序不仅难以编写, 效率 
还很低.

\section{结论}
\label{sec:conclusion}
虽然 awk 不能解决所有的编程问题, 但它却是程序员的必备工具之一, 尤其是
在 Unix (在 Unix 中要经常用到各种工具). 也许书中的大程序给你留下了些
不同的印象, 但是大多数 awk 程序其实非常简短, 而且所执行的任务本来就是
当初开发 awk 的目标: 计数, 数据格式转换, 计算, 以及从报表中提取信息.

对于上一段中提到的任务, 程序的开发时间比运行时间更加重要, 在这一方面
awk 难逢敌手. 隐式输入循环和 \patact 范式简化了 (而且经常是完全消除了)
流程控制语句. 字段分割操作处理最常见的输入数据形式, 而数值和字符串, 以
及它们之间的类型转换处理最常见的数据类型. 关联数组同时提供了传统的数组
存储功能和灵活的下标. 正则表达式提供了描述文本的统一表示法. 默认的初
始化操作和声明的缺少缩减了程序的规模.

我们没有料到的是, 在许多非常规应用中也用到了 awk. 比如 ``非编程'' 到
``编程'' 的转换是一个渐变的过程, 由于缺少传统语言 (比如
C 和 Pascal) 所具有的语法包袱, 所以 awk 学习起来非常简单, 它甚至是相
当一部分人的第一门编程语言.

在 1985 年加入的特性, 尤其是自定义函数的支持, 催生出了许多未曾预料到的
应用, 比如小型数据库系统和小语言编译器. 在许多种情况下, awk 只是用
于构造原型, 测试想法的可行性, 以及对特性和用户接口进行评测, 即使如此,
在某些情况下, awk 程序仍然可以被当作一件真正的产品使用. Awk 甚至被用
到了软件工程课程中, 因为和大型语言相比, 使用 awk 对设计进行实验可能会
更加方便.

当然, 我们要小心不能走得太远 --- 任何工具都有极限 --- 但是很多人已经
发现, awk 是解决许多问题的有用工具, 我们希望本书所介绍的使用方法, 对
读者来说同样有用.

\marginpar{186}
\subsection*{参考资料}

本书作者写的 ``AWK --- a pattern scanning and processing language'' 描述
了 awk 的原始版本, 载于 \textit{Software --- Practice and Experience},
1979 年 4 月, 这篇文章还包括了和语言设计有关的技术性讨论.

Awk 的大部分语法来源于 C 语言, \textit{The C Programming Language} 
(B. W. Kernighan 和 D. M. Ritchie 著, Prentice-Hall 1978 年出版)
对 C 语言进行了完整的讨论. \texttt{egrep}, \texttt{lex} 和 \texttt{sed}
使用的正则表达式在 \textit{The Unix Programmer's Manual} 的第 2 部分中
讨论. \textit{Compilers: Principles, Techniques, and Tools} (Aho, Seti, 
和 Ullman 著, Addision-Wesley 1986 年出版) 的第 3 章包含了一个关于正
则表达式模式匹配的讨论, 新版本的 awk 就用到了该技术.

也许你会觉得把 awk 和其他类似的语言作对比会比较有趣, 这些语言的元老当然
是 SNOBOL4, \textit{The SNOBOL4 Programming Language} (R. Griswold, J.
Poage, 和 I. Polonsky 著, Prentice-Hall 1971 年版) 对该语言进行了详细
的讨论. 虽然 SNOBOL4 苦于应付非结构化的输入语言, 但它仍然是一门非常
强大, 灵活的编程语言. ICON (详情见 R. Griswold 和 M. Griswold 所著的
\textit{The ICON Programming Language}, Prentice-Hall 1983 年出版) 是
SNOBOL4 的直系后代, 它有着更友好的语法规则, 也集成了更多的模式设施.
IBM 系统的解释语言 REXX 是另一个例子, 虽然它更想把自己当作
一个 shell 或命令解释器, 详情请参考 \textit{The REXX Language} (M. F.
Cowlishaw 著, Prentice-Hall 1985 年出版).