Interpreting the Data:Parallel Analysis with Sawzall（2）

7．Sawzall语言概览
作为一种查询语言，Sawzall是一种类型安全的脚本语言。由于Sawzall自身处理了很多问题，所以完成相同功能的代码就简化了非常多-与MapReduce的C++代码相比简化了10倍不止。

Sawzall语法和表达式很大一部分都是从C照搬过来的；包括for循环，while循环，if语句等等都和C里边的很类似。定义部分借鉴了传统Pascal的模式：

i:     int    ;      # a simple integer declaration;

i:     int=0;      # a declaration with an initial value;

基本类型包括整数（int），是64位有符号值；浮点数（float），是一个double精度的IEEE浮点数；以及很类似整数的time和fingerprint。time是毫秒级别的时间，并且函数库包括了对这个类型的转换和操作。fingerprint是一个执行定义的hash值，可以很容易通过建立数据的fingerprint来构造聚合器索引。

同时，Sawzall也有两种基本的数组类型：bytes，类似C的unsigned char的数组；string，string用来存放UNICODE的字符串。在Sawzall中没有”字符”类型；byte数组和string的基本元素是int，而虽然int的容量远比字节或者字符串的基本元素来得大。

复合类型包括数组，maps（本文档中是可以重载概念），tuples。数组是用整数作为下标检索的，maps是结合了数组或者Python字典的类型，可以用任意类型检索，可以根据需要建立无序的索引。最后tuples是对数据的任意分组，类似C或者PASCAL的结构类型。任何类型都可以有一个正式的名字。

类型转换操作是把数据从一种类型转换成为另一种类型，并且Sawzall提供了很广泛的类型转换。例如，把一个字符串表示的浮点数转换成为一个浮点数：

f: float;

s: string = "1.234";

f = float(s);

部分转换是可以带参数的：

string(1234, 16)

就可以把一个整数转换成为一个16进制的字符串。并且：

string(utf8_bytes, "UTF-8")

转换一个UTF-8的byte数组成为一个unicode字符串。

为了方便起见，并且为了避免某些语言定义上的啰嗦，编译器可以在初始化定义的时候隐含的左适当的转换操作（使用缺省的转换参数）。因此：

b: bytes = "Hello, world!\n";

等价于显示的转换：

b: bytes = bytes("Hello, world!\n", "UTF-8");





任何类型的值都可以转换成为字符串，这是为了调试的方便考虑。

Sawzall最重要的转换是和协议buffer相关的。Sawzall有一个编译时刻参数：proto，有点类似C的#include指令，可以从一个定义了Sawzall tuple类型的文件加载DDL协议buffer。通过tuple描述，就可以转换输入的协议buffer到Sawzall的值了。

对于每一个输入记录，解释器都需要把这个由二进制数组表达的值初始化到特定的输入变量中，尤其是转换到协议buffer类型的输入变量中去。Sawzall程序对于每一个记录的执行都是由下边这条语句隐式执行的：

input: bytes = next_record_from_input();

因此，如果文件：some_record.proto包含了类型Record的协议buffer的定义，那么下边的代码会把每一个输入记录分析道变量r中：

proto "some_record.proto" # define ’Record’

r: Record = input; # convert input to Record

Sawzall有很多其他的传统特性，比如函数以及一个很广泛的选择基础函数库。在基础函数库中是给调用代码使用的国际化的函数，文档分析函数等等。



7.1．输入和聚合


虽然在语句级别Sawzall是一个很传统的语言，但是它有两个非常不寻常的特性，都在某种意义上超越了这个语言本身：

1．  Sawzall程序定义了对于数据的单个记录的操作。这个语言没有提供任何可以同时处理多条记录的方法，以及没有提供通过一个输入记录的值来影响另一个记录的方法。

2．  这个语言为一个输出时emit语句，这个语句发送数据到一个外部的聚合器来汇聚每一个记录的结果并且在聚合器进行结果的加工和处理。

因此普通的Sawzall程序行为是使用输入变量，用转换操作把输入的记录分析到一个数据结构，检查数据，并且处理成一些值。我们在第三节可以看到这种模式的一个简单例子。

下边是一个更有代表性的Sawzall程序例子。对于给定的我们原代码管理系统的源代码提交记录集合，这个程序会用分钟级别的分辨率，给出周的提交变化频率表。

proto "p4stat.proto"

submitsthroughweek: table sum[minute: int] of count: int;

log: P4ChangelistStats = input;

t: time = log.time; # microseconds

minute: int = minuteof(t)+60*(hourof(t)+24*(dayofweek(t)-1));

emit submitsthroughweek[minute] <- 1;

这个程序一开始从文件p4stat.proto引入了协议buffer描述。在这个文件中定义了类型: P4ChangelistSTats(程序员必须明确知道这个类型是从proto引入的，而且还要知道这个是由协议bufferDDL定义的)

接下来就是定义了submitsthroughweek。它定义了一个sum值得table，这个table使用一个整数minute作为下标。注意index值在table定义的时候是给出了一个可选的名字（minute）。这个名字没有任何语义，但是使得这个定义更容易理解，并且提供了一个聚合输出的域标签。



log的定义把输入的byte数组转换成为Sawzall的类型：P4ChangelistStats,这个转换是用（proto语句引入的代码转换的），这个类型是tuple类型，保存在输入变量log里边。接着我们把time值取出来，并且接着就保存到变量t中。

接下来的定义有着更复杂的初始化表达式，这个表达式使用了一部分内嵌的函数，用来从time值来计算基准的周分钟基线数字[2]。

最后，emit语句通过增加该分钟的数字来统计这个提交情况。

总结一下，这个程序，对于每一个记录，都取得时间戳，把时间转换成为本周的分钟数，然后在这周的对应分钟发生次数增加1。并且，隐式的，这个会重新取下一个记录进行循环处理。

当我们在全部的提交日志上运行这个程序，这个记录跨越了很多个月，并且输出结果，我们可以看到一个按照分钟区分的聚合的周活动趋势。输出结果可能像这样的：

submitsthroughweek[0] = 27

submitsthroughweek[1] = 31

submitsthroughweek[2] = 52

submitsthroughweek[3] = 41

...

submitsthroughweek[10079] = 34

当使用图像表达，那么这个图就像图三一样。

我们举这个例子要表达的意思当然不是说这个提交源码的频率数据如何如何，而是说这个程序怎样产生抽取这个数据出来。




图3：周源代码提交频率。本图从周一早上凌晨0点开始。



7.2．聚合器补充说明
因为某些原因，我们在本语言之外完成聚合。应该由一个传统的语言来用语言处理能力本身来处理结果，但是由于聚合的算法可能会相当的复杂，最好用某种形式的机器语言来实现。更重要的是，虽然在语言层面上隐藏了并行的机制，但是在过滤阶段和聚合阶段划一条清晰的界限能够有助于更高级别的并行处理。在Sawzall中不存在记录的多样性的，在Sawzall典型任务就是在上百或者上千台机器上并发操作上百万条记录，

集中精力在聚合器上可以创造出很不寻常的聚合器。现在已经有许多聚合器；下边是一个不完整的列表：

● 搜集器

       c:    table collection of string;

一个简单的输出结果列表，这个结果在列表中是任意顺序的。

● 采样器

       s:    table sample(100) of string

类似搜集器，但是存的是无偏差的输出结构的采样值。这个采样的大小是用参数体现的。

● 累加

       s:    table sum of (count:int,revenue:float);

所有输出结果的合计。这个输出结果必须是算数的或者可以以算术为基础的（也就是可累加的，by 译者），就像例子中的tuple结构那样（也就是说一般可以是sum of int,也可以像上边说的一样，可以用sum of (count:int,revenue:float)这样的tuple结构。对于复合值，元素是按照内部的项进行累加的。在上边的例子，如果count始终为1，那么平均revenue可以在处理完和以后用revenue除以count来得到。

● 最大值

       m:   table maximum(10) of string weight length: int;

取得最大权重的值。每一个值都有一个权重，并且最终选择的值是根据最大权重来选择的。这个参数（例子中是10）规定了需要保留的最终输出的值数量。权重是以明确的keyword来描述的，并且它的类型（这里是int）是在这里定义的，它的值是emit语句给出的。对上边例子来说，emit语句如下：

       emit m <- s weight len(s);

这样将会在结果中放置最长的字符串。

● 分位数

       q:    table quantile(101) of response_in_ms:int;

是用输出的值来构造一个每个概率增量分位数的累计概率分布（算法是一个Greenwald和Khanna的分布式算法[10]）。这个例子可以用来查看系统的响应变化的分布情况。通过参数101，这个参数用来计算百分点。第50个元素是中间点的响应时间，第99个元素是99%的响应时间都小于等于第99个元素。

● 最常见

       c:    table top(10) of language: string;

top table评估这个值是否最常见（与之对应的，maximun table找到最高权重的值，而不是最常见的值）

例如：

       emit t <- language_of_document(input);

将会从文档库中建立10个最常见的语言。对于很大的数据集来说，它可能需要花费过大的代价来找到精确的出席频率的order，但是可以有很有效的评估算法。top table是用了Charikar,Chen,Farach-Colton[5]的分布式算法。算法返回的最常见的频率是极为接近真实的出现频率。因为它的交换性和结合性也不是完全精确的：改变处理的输入记录先后顺序确实会影响到最终的结果。作为弥补措施，我们在统计元素个数之外，也要统计这些个数的误差。如果这个误差和元素个数相比比较小，那么结果的正确度就比较高，如果错误相对来说比较大，那么结果就比较差。对于分布不均匀的大型数据集来说，top table工作的很好。但是在少数情况下比如分布均匀的情况下，可能会导致工作的不是很成功。



● 取唯一

       u:    table unique(10000) of string;

unique table是比较特别的。它报告的是提交给他的唯一数据项的估计大小。sum table可以用来计算数据项的总和个数，但是一个unique table会忽略掉重复部分；最终计算输入值集合得大小。unique table同样特别无论输入的值是什么类型，它的输出总是一个count。这个参数是给出了内部使用的table大小，这个是用来内部作评估是用的内部表；10000的参数值会让最终结果有95%的概率正负2%的误差得到正确的结果（对于N，标准偏差是大概N*参数**(-1/2)）



有时候也会有新的聚合器出来。虽然聚合器用处很大，但是增加一个新的聚合器还算容易。聚合器的实现复杂在需要支持所有解释器所支持的数据类型。聚合器的实现还需要效验某些类型（校验参数值和元素类型），并且对保存和读取数据作打包。对于简单的聚合器，类似sum，就没有什么其他的要求了。对于更复杂的聚合器，类似分位数和top，必须注意要选择一个符合交换律和结合律的算法，并且这个算法要在分布式处理上有足够的效率。我们最小的聚合器实现上大概只用了200行C++代码，最大的聚合器用了大概1000行代码。

有些聚合器可以作为map阶段来处理数据，这样可以降低聚合器的网络带宽。例如sum table可以本地作各个元素的累加，只是最后把本部分的小计发往远端的聚合器。用MapReduce的词语来说，这就是MapReduce的合并阶段，一种在map和reduce中间的优化阶段。



7.3．带索引的聚合器


聚合器可以是带索引的，这个可以使得每一个索引下标的值都有一个单独的聚合器。这个index可以是任意的Sawzall类型，并且可以是一个聚合器的多维的结构下标。

例如，如果我们检查web服务器的log，table：

table top(1000)[country:string][hour:int] of request:string;

可以用来找到每一个国家每一个小时的最常用的请求字串。

当新的索引值产生的时候，就会动态产生一个独立的聚合器，某种意义上比较类似map，但是是和所有运行的机器无关。聚合阶段会比较每一个索引下标对应的值，并且产生适当的聚合值给每一个索引值。

作为整理的一部分，数据值将按照索引排序，这样使得从不同机器上合并最终结果比较容易。当任务完成的时候，输出值就按照索引进行排序了，这就意味着聚合器的输出是索引顺序的。

index本身就是构造了一个有用的信息。就像上边讲述的web服务器的例子，当运行完以后，在country索引的记录中就构造了请求接收到的国家集合。另外，index的引入使得可以用index对结果集进行分类。table sum[country:string] of int产生的索引结果将会等同于去掉重复项以后的table collection of country:string的结果值。









8．System Model
下边介绍本语言的基本特性，通过对数据分析的建立，我们可以给出高级别的系统模式概览。

系统运行是基于一个批处理的模式的：用户提交一个工作，这个工作分布在一个固定的文件集合上，并且在执行完成以后搜集输出的结果。输入格式和数据源（通常是文件集）以及输出目标都是在程序语言外指定的，通过执行工作的参数形式来递交给系统进行执行。

当系统接收到一个工作请求，Sawzall处理器就开始效验这个程序是否语法正确。如果语法正确，源代码就发送给各个将被执行的机器，每一个机器就开始分析代码并且开始执行。

每一个执行的机器的输出都分不到一组文件中，每一个文件都部署在一个聚合器机器上。这个输出结果拆分到不同的机器上，是为了能让聚合器并行工作。我们给予特定的table和他上边的相关索引来确定这些分布在各个文件中的值。

基于table的类型，输入table的值可以是最终格式的值，也可以是某种中间结果的值，这些中间结果便于进行合并或者处理。这种合并处理必须能够良好的结合起来才能工作的一个步骤。某些工作由于十分巨大，而结合率允许他们拆成多个小块，并行运行，最后再合并在一起。（这是本系统的一个优势，优于平坦模式的MapReduce;因为MapReduce可能会在一个需要运行几天几周的任务上出问题）

通常，分解处理以后的数据要比输入要小得多，但是也会有某些关键的应用不是这样的。例如，我们的程序可以用一个带索引的collection table来对数据作多维的组织，在这样的情况下，输出结果就可能比输入要多。

Sawzall中一个常用的输入是把结果数据注入一个传统的关系数据库中，以备后续的分析。通常这些都是有不同的用户程序来注入，也许是用Python，它把数据转换成为通过SQL指令建立的表。我们以后也许会提供更多的直接方法来完成八结果注入到数据库的动作。

Sawzall的结果有时也用于其它Sawzall程序的输入，这个就是链式处理。链式处理的简单例子就是精确计算输出的”top 10”列表。Sawzall的top table虽然高效，但是他不精确。如果需要精确的结果，那么就需要分为两个步骤。第一步创建一个带索应的sum table来统计输入值得频率；第二个步骤是用一个maximum table来选择最常见的频率。这样可能有点笨，但是这种方法依旧是非常高效的方法来计算多维的table。



9．例子
这里是另外一个完整的例子，演示了Sawzall在实际中如何使用。这里是处理一个web文档库，并且产生一个结果：对于每一个web服务器，那一个page有着最高的Page Rank[13]？答曰来说，那一个是最多link指向的page？

proto       “document.proto”

max_pagerank_uri:

       table maximun(1)[domain:string] of url:string

              weight pagerank:int;

doc: Document = input;

url:   string = doc.url;

emit max_pagerank_url[domain(url)] <- url

       weight doc.pagerank;





protocol buffer 的格式是在”document.proto”中定义的。这个table是max_pagerank_url，并且会纪录每一个索引中最高权重的值。这个索引是domain，值是URL，权重势document的PageRank。程序处理输入的纪录，解出URL，并且执行相关的emit语句。它会调用库函数 domain(url)来解出URL所对应的domain，并且使用这个domain作为index，把URL作为值，并且用这个document对应的PageRank作为权重。

当这个程序在一个数据仓库上运行的时候，输出对于大部分site，most-linked网页是www.site.com-真是令人惊讶。Acrobat 下载站点是adobe.com的top page，并且连接到banknotes.com的就是连接到连接最多的图库站点，并且bangkok-th.com是最多引用的ye生活page。

因为是用Sawzall能简单表达这样的计算，所以程序是又简洁又优美。即使用了MapReduce,等价的C++程序也要好几百行代码。

下边是一个例子，使用了多维索引的聚合器。我们目的是通过检索搜索log，建立一个查询发起点的世界地图。

proto       “querylog.proto”

queries_per_degree: table sum[lat:int][lon:int] of int;

log_record:     QueryLogProto = input;

loc:                Location = locationinfo(log_record.ip);

emit queries_per_degreee[int(loc.lat)][int(loc.lon)] <- 1;



这个程序相当直接，我们引入查询log的DDL，定义一个用了经纬作索引的table，并且从log中解包查询。接着我们是用内嵌函数把这个IP地址对应到请求及其的位置（可能是ISP的位置），并且为每一个经纬点增加1。int(loc.lat)把loc.lat，一个浮点值转换成为一个整数，截断成为一个维数下标。对于高分辨的地图来说，可能要求更精细的计算。

这个程序的输出是一个数组，可以用来构造一个地图，参见图4。



10．执行模式
在语句级别，Sawzall是一个常规的语言，但是从更高的角度看，他有一些特点，所有的设计目的都是为了并行计算。

当然，最重要的是，一次处理一个纪录。这就意味着，其他纪录的处理将不消耗额外的内存（除了在语言本身外把结果提交给聚合器）。Sawzall在上千台机器上并行执行，是Sawzall的一个设计目的，并且系统要求这些机器之间没有额外的通讯。唯一的通讯就是从Sawzall的执行结果下载到聚合器。






图四：查询分布

为了强调这点，我们用计算输入记录数的数量来入手。就像我们之前看到的这个程序：

count:     table sum of int;

emit count <- 1;



这个程序将完成统计记录数的工作。与之对比的是，如下的一个错误的程序：

count:     int = 0;

count ++;

这个程序将不能统计记录数，因为，对于每一个记录来说，count都被设置成为0，然后再++，最后结果就扔掉了。当然，并行到大量机器上执行，扔掉count的效率当然很高。

在处理每一个记录之前，Sawzall程序都会回到初始的状态。类似的，处理完成一条记录，并且提交了所有的相关的数据给聚合器后，任何执行过程中使用到的资源—变量—临时空间等等—都可以被废弃。Sawzall因此使用的是一个arena allocator[11](单向递增分配，场地分配策略，就是说，从一个内存池中通过单向增加一个指针的方式来分配内存，类似零散内存的管理方式)。当一个记录都处理完成之后，就释放到初始状态。

在某些情况下，重新初始化是不需要的。例如，我们可能会创建一个很大的数组或者影射表来对每条记录进行分析。为了避免对每条记录都作这样的初始化，Sawzall有一个保留字static可以确保这个变量只初始化一次，并且是在处理每条记录的最开始的初始化的时候执行。这就是一个例子：

static      CJK: map[string] of string = {

       “zh” : “Chinese”,

       “jp”:”Japanese”,

       “ko”,”Korean”,

       };



CJK变量会在初始化的时候创建，并且作为处理每条记录的初始化的时候都保留CJK变量的值。

Sawzall没有引用类型；它是纯粹值语义的。数组和maps也可以作为值来是用（实现的时候，在大部分情况下，用copy-on-write引用计算来提高效率）。某些时候这个比较笨拙-在一个函数中修改一个数组，那么这个函数必须返回一个函数-但是在典型的Sawzall程序中，这个并没有太大的影响。但是这样的好处，就可以使得并发处理记录的时候，不需要担心同步问题或者担心交叉使用的问题，虽然实现上很少会用到这个情况。



11．语言的Domain相关特性


为了解决domain操作的问题，Sawzall有许多domain相关的特性。有一部分已经讨论过了，本节讨论的是剩下的一部分。

首先，跟大部分”小语言”[2]所不同，Sawzall是一个静态类型语言。主要是为了可靠性的考虑。Sawzall程序在一次运行中，会是用数小时，乃至好几个月的CPU时间，一个迟绑定（late-arising）动态类型错误导致的代价就有可能太大。另外，还有一个潜在的原因，聚合器使用完整的Sawzall类型，静态类型会让聚合器的实现比较容易。类似的争议也在分析输入协议buffer上；静态类型可以精确检测输入的类型。同样的，也会因为避免了运行时刻动态类型检测而提高整个的性能。最后，便以时候类型检查和强制类型转换要求程序员精确的指出类型转换。唯一的例外是在变量初始化的时候，但是就算在这个时候，类型以就是清晰而且程序也是类型安全的。

从另外的角度上看，强类型保证了变量的类型一定可知，在初始化的时候容易处理。例如：

t:     time=”Apr 1 12:00:00 PST 2005”;

这样的初始化就很容易理解，而且还是类型安全的。并且有一些基本类型的属性也是主机相关的。比如处理log记录的time stamps的时候，这个time基本类型就是依赖于log记录的time stamps的；对于它来说，如果要支持夏令时的时间处理就太过奢侈了。更重要的是（近来比较少见了），这个语言定义了用UNICODE表示string，而不是处理一组扩展字符集编码的变量。

由于处理大量数据集的需要，我们有赋予这个语言两个特性：处理未定义的值，处理逻辑量词。下两节详细描述这个特性。

11.1 未定义的值


Sawzall没有提供任何形式的异常处理机制。相反，他有自己的未定义值得处理概念，用来展示错误的或者不确定的结果，包括除0错，类型转换错误，I/O错误，等等。如果程序在初始化以外的地方，尝试去读一个未定义的值，它会崩溃掉，并且报告一个失败。

def（）断言，用于检测这个值是否一定定义了；如果这个值是一个确定值，他返回true，否则返回false。他的通常用法如下：

v: Value = maybe_undefined();

if (def(v)) {

       compute(v);

}

下面是一个必须处理未定义值得例子。我们在query-mapping程序中扩展一个时间轴。原始程序使用函数locationinfo()来通过外部数据库判定IP地址的位置。当IP地址不能在数据库中找到的时候，这个程序是不稳定的。在这种情况下，locationinfo()函数返回的是一个不确定的值，我们可以通过使用def()断言来防止这样的情况。



下边就是一个简单的扩展：

proto "querylog.proto"

static RESOLUTION: int = 5; # minutes; must be divisor of 60

log_record: QueryLogProto = input;

queries_per_degree: table sum[t: time][lat: int][lon: int] of int;

loc: Location = locationinfo(log_record.ip);

if (def(loc)) {

       t: time = log_record.time_usec;

       m: int = minuteof(t); # within the hour

       m = m - m % RESOLUTION;

       t = trunctohour(t) + time(m * int(MINUTE));

       emit queries_per_degree[t][int(loc.lat)][int(loc.lon)] <- 1;

}

（注意，我们只是简单的扔掉我们不知道的位置，在这里是一个简单的处理）。在if后边的语句中，我们用了一些基本的内嵌函数（内嵌常数：MINUTE），来截断记录中的time stamp的微秒部分，整理成5分钟时间段。

这样，给定的查询log记录会扩展一个时间轴，这个程序会把数据构造多一个时间轴，这样我们可以构造一个动画来展示如何随着时间变化而查询位置有变化。

有经验的程序员会使用def()来保护常规错误，但是，有时候错误混杂起来会很怪异，导致程序员很难事先考虑。如果程序处理的事TB级别的数据，一般都会有一些数据不够规则；往往数据集的数据规则度超乎作分析程序的人的控制，或者包含偶尔当前分析不支持的数据。在Sawzall程序处理的情况下，通常对于这些异常数据，简单丢弃掉是最安全的。

Sawzall因此提供了一种模式，通过run-time flag的设置，可以改变未定义值得处理行为。通常，如果遇到一个未定义的值（就是说没有用def()来检测一下），将会终止程序并且会给出一个错误报告。当run-time flag设置了，那么，Sawzall简单的取消这个未定义的值相关的语句的执行。对于一个损坏的记录来说，就意味着对临时从程序处理中去除一样的效果。当这种情况发生的时候，run-time会把这个作为日志，在一个特别的预先定义的Collection table中记录。当运行结束的时候，用户可以检查错误率是否可以接受。对于这个flag的用法来说，还可以关掉这个flag用于调试-否则就看不到bug！-但是如果在一个大数据集上运行的时候，还是打开为妙，免得程序被异常数据所终止。

设置run-time flag的方法是不太常见的错误处理方法，但是在实际中非常有用。这个点子是和Rinard etal[14]在gcc编译器生成容错代码有点类似。在这样的编译器，如果程序访问超过数组下表的索引，那么生成的代码可以使得程序能够继续执行。这个特定的处理方式参考了web服务器的容错设计的模式，包括web服务器面临恶意攻击的健壮性的设计。Sawzall的未定义值得处理增加了类似的健壮性设计级别。

11.2 量词


虽然Sawzall是基于单个记录的操作，这些记录可能会包含数组或者结构，并且这些数组或者结构需要作为单个记录进行分析和处理。哪个数组元素有这个值？所有值都符合条件？为了使得这些容易表达，Sawzall提供了逻辑量词操作，一组特定的符号，类似”for each”,”for any”,”for all”量词。

在when语句的这种特定的构造中，可以定义一个量词，一个变量，和一个使用这个变量的布尔类型的条件。如果条件满足，那么就执行相关的语句。量词变量就像普通的integer变量，但是它的基础类型（通常是int）会有一个量词前缀。比如，给定数组a，语句：

when(i: some int; B(A[i]))

       F(i);

就会当且仅当对于一些i的取值，布尔表达式B(a[i])为TRUE的情况下，执行F（i）。当F（i）执行了，他会被绑订到满足条件的值。对于一个when语句的执行来说，要求有求值范围的一个限制条件；在这个例子中，隐式的指出了关于数组的下标就是求值的范围。在系统内部实现上，如果需要，那么系统使用def()操作来检查边界。

一共有三个量词类型：some，当有任意值满足条件的时候执行（如果超过一个满足条件，那么就任选一个）;each,执行所有满足条件的值；all，当所有的值都满足条件的时候执行（并且不绑定值到语句体）。

when语句可能包含多个量词，通常可能会导致逻辑编程的混淆[6]。Sawzall对量词的定义已经足够严格了，在实际运用中也不会有大问题。同样的，当多重变量出现的时候，Sawzall规定他们将按照他们定义的顺序进行绑定，这样可以让程序员有一定的控制能力，并且避免极端的情况。

下边是一些例子。第一个测试两个数组是否共享一个公共的元素：

when(i, j: some int; a1[i] == a2[j]) {

...

}

第二个例子扩展了这个用法。使用数组限制，在数组的下标中使用用:符号来限制，他测试两个数组中，是否共享同样的3个或者更多元素的子数组：

when(i0, i1, j0, j1: some int; a[i0:i1] == b[j0:j1] &&i1 >= i0+3) {

...

}

在类似这样的测试中，不用写处理边界条件的代码。即使数组小于三个元素，这个语句依旧可以正确执行，when语句的求值可以确保安全的执行。

原则上，when语句的求值处理是可以并行计算的，但是我们还没有研究这方面的内容。



本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/zhujt1981/archive/2008/04/04/2249931.aspx