Filters, sources and sinks: design, motivation and examples
or Functional programming for the rest of us
by DiegoNehab
应用程序有时有太多的信息需要在内存处理，即使现在已经有足够的内存，也会被迫把数据分成小部分处理。，以原子方式处理所有数据可能需要很长的时间，这妨碍了用户与应用程序交互。复杂的数据转换往往可以被定义为一系列简单的操作。几个不同的复杂的转换可以共享相同的更简单的操作，因此，定义一个统一的接口，把他们组合起来，是很好的处理方法。以下概念构成我们对这些问题的解决方案。
Filters是一些函数，接受连续块的输入，并产生连续的输出块。此外，连接所有的输出数据作为输入数据的级联filter应用的结果是相同的。因此，边界是无关紧要的：Filters必须处理由用户任意分割的输入数据。
chain是一个函数，将两个（或更多）的函数连接起来，但其接口和其他函数组件的接口没有什么区别。因此，链式Filters可用于任何一个可以使用原子Filter的地方。然而，其对数据的影响是其组成的filters的综合效果。请注意， chain可以连接其他的chain，创建任意复杂的操作，而像原子操作那样使用。
Filter可以被看作是通过它的数据流在网络内部的节点，并且可能根据不同的filter对数据进行转换。把这些节点链接起来，组成完整的网络数据流图。为此我们需要添加初始和最终的网络节点，分别是source和sink。具体来说，source是一个函数，每次调用时产生新的数据。相应的，sink函数是接收到的数据的最终目的地。source和sink可以使用chain和filter相连。
总的来数，Filter，chain，source和sink，都是被动的实体：他们需要被重复调用以便使系统运行起来。Pumps提供了推动数据流过网络的动力，从一个source到一个sink。
我们希望，通过例子使这些概念将变的清晰。在下面的章节中，我们从一个简单的接口开始，不断的完善这个接口，直到没有明显的缺点。我们做出的演化不是人为强制的：它按部就班，巩固了我们对这些概念的理解。
1 一个具体的例子
一些数据转换操作容易用Filter方式来实现，比如行结束的文本标准化，Base64和Quoted-Printable传输内容的编码，把文本切分成行，SMTP字节填充等等。
我们将要定义第一个filter接口，“行结束符标准化”。稍后我们讨论为什么实现起来并不容易。
假设我们得到一个文本，含有未知的行结束符，比如常见的Unix（LF）的Mac操作系统（CR）和DOS（CRLF）（包括可能的混合情况）。我们希望能够编写如下代码：
input = source.chain(source.file(io.stdin), normalize(\)) output = sink.file(io.stdout) pump(input, output)
这个程序从标准输入流中读取数据和行结束标记，用CRLF （MIME标准定义的标记）标准化,最后将结果发送到标准输出流。为此，我们使用一个标准输入：stdin，一个Filter：normalize，组成chain。然后执行pump调用，不断从stdin获取数据，并将其输送到sink：标准输出。
为了使讨论更具体，我们从讨论如何实现一个标准化Filter开始，这个normalize是一个函数，它用于创建一个filter功能。我们初步的filter接口如下：filter接收输入数据块，并返回处理的数据块。在没有更多的输入数据时，用户通知filter，用nil作为参数来调用它。filter返回最后的数据块。
虽然接口极其简单，实现似乎并不那么简单明确。任何遵守此接口的过滤器需要保持某种在调用之间的上下文。这是因为数据块可以越过标记一行的末尾之间的CR和LF字符。这个上下文存储的需求，促成了工厂函数的使用：每个工厂函数被调用时，返回一个filter，具有它自己的上下文，如此使我们可以在同一时间得到多个独立的filter。对于这个normalize filter，我们意识到，简单明了的解决方案是不够的（例如，在产生任何输出之前，把所有输入连接起来放入上下文中），我们将不得不寻找另一种方式。
我们将实现分为两部分：一个低级别的filter，和一个高级别的filter工厂。低级别的filter将在C实现，不会携带任何函数调用之间的上下文。高级别filter的工厂，在Lua中实现，filter工厂将创建并返回高级别的filter，它为低级别的filter提供上下文，但其内部细节对用户隔离。这样，我们利用C的效率优势，进行底层工作，利用lua的简单性做上下文记录。
1.1 Lua 部分的实现
function filter.cycle(low, ctx, extra) return function(chunk) local ret
-- ctx上下文只对low底层filter有用处，每次调用通过返回值更新 ret, ctx = low(ctx, chunk, extra)
-- 返回处理结果 nil表示处理完毕，没有更多数据了 return ret end end
2
function normalize(marker) return cycle(eol, 0, marker) end
normalize工厂函数只是简单地调用一个更加通用的名叫cycle的工厂。这个工厂接收一个低级别的filter，一个初始上下文和一些额外的值，并返回相应的高级别filter。高级别Filer使用一个新的数据块作为参数被调用，它调用低级别的过滤器，传递上一次的上下文，新的数据块和额外的参数。低级别的Filer生成处理过的数据块和一个新的上下文。最后，高级别Filer更新其内部上下文，返回处理过数据块给用户。低级别的过滤器完成了所有的工作。请注意，这个实现，利用了Lua5.0词法作用域规则，在函数调用之间存储本地上下文。
思考一下这个低级别的filter，我们注意到行结束标记标准化问题本身没有完美的解决方案。困难来自一个空行定义，它固有的模糊性。然而，以下的解决方案非常适用于任何情况的输入，以及混合输入的非空行。它作为一个很好的例子，如何实现一个低级别的过滤器。
这是我们所做的：CR和LF被认为是换行符的候选字符。我们认为这样得到得到一个结束标记：如果候选字符是单独的一个，或后面跟着一个不同的候选字符。也就是说，CRCR和LFLF被认为是两个行结束标记，但CR LF和LFCR的被认为只是一个结束标记。这个方法可以照顾到Mac OS，Mac OS X，VMS和Unix，DOS和MIME，以及其他可能更晦涩的约定的系统。
1.2 C部分实现
低级别的filter划分为两个简单的函数。内部函数完成实际的转换，他判断每一个输入字符，并决定了输出什么，以及如何修改上下文。上下文告知最后一个字符是否是候选字符，若是，是哪个候选字符。 #define candidate(c) (c == CR || c == LF)
static int process(int c, int last, const char *marker, luaL_Buffer *buffer) { if (candidate(c)) {
if (candidate(last)) {
//相同候选字符，添加一个标准化maker（CRLF）返回非换行符0 if (c == last) luaL_addstring(buffer, marker); return 0; } else {
//不同候选字符，添加一个标准化maker（CRLF）返回是当前换行符字符 luaL_addstring(buffer, marker); return c; } } else {
//不是候选字符，读入这个字符,返回非换行符0 luaL_putchar(buffer, c); return 0; }
3
}
内部函数 使用Lua的辅助库的缓冲接口,带来了效率和易用性。外部函数简单地使用Lua交互接口。它接收上下文和输入数据块（以及一个可选的行结束标记），并返回转换后的输出和新的上下文。 static int eol(lua_State *L) {
-- 上下文表示得到的最后一个换行符是什么，CR,LF,或者非换行符（用0表示） int ctx = luaL_checkint(L, 1); size_t isize = 0;
const char *input = luaL_optlstring(L, 2, NULL, &isize); const char *last = input + isize;
const char *marker = luaL_optstring(L, 3, CRLF); luaL_Buffer buffer;
luaL_buffinit(L, &buffer); if (!input) {
-- 输入块为nil，重置ctx为nil，返回上次的字符为0，表示非换行符 lua_pushnil(L);
lua_pushnumber(L, 0); return 2; }
while (input < last)
-- 逐个字符读入判断，进行标准化
-- ctx 表示上一次读入的字符，CF，LF，非换行符用0表示 ctx = process(*input++, ctx, marker, &buffer); luaL_pushresult(&buffer); lua_pushnumber(L, ctx); return 2; }
请注意，如果输入块是nil，操作将被视为完成。在这种情况下，循环将不会执行并且上下文被重置到初始状态。这使得过滤器可以被被无数次重用。这是一个不错的主意，如果可能就像这样写过滤器。
除了行结束标准化如上所示的过滤器，许多其他过滤器可以按照同样的思路实现。比如Base64和Quoted-Printable的内容传输编码，文本断行，SMTP字节填充等。具有挑战性的部分是决定用什么作为上下文。例如文本断行，它可能是留在当前行的字节数。比如Base64编码，它可能是在输入字节中以3个字节为单位进行分割的字节串。 2 链接起来
chain的概念引入后，Filer变得更加强大。假设你有一个Quoted-Printable编码的Filer，你要编码一些文字。根据要求，文本必须在编码前标准化为标准范式。简化任务的一个很好的接口是创建一个工厂，工厂创建一个组合过滤器，数据经过多个过滤器进行传递，同时还可以作为一种最初的简单过滤器来使用。 local function chain2(f1, f2) return function(chunk)
4
local ret = f2(f1(chunk)) if chunk then return ret
else return ret ... f2() end – 这里使用...有问题，看做是伪码 end end
function filter.chain(...) local f = arg[1]
for i = 2, table.getn(arg) do f = chain2(f, arg[i]) end return f end
local chain = filter.chain(normalize(\), encode(\)) while 1 do
local chunk = io.read(2048) io.write(chain(chunk))
if not chunk then break end end
chain的工厂是非常简单的。它的作用是返回一个函数，这个函数把数据传递通过所有的filter，并将结果返回给用户。它使用简单的辅助函数，知道如何链接两个过滤器。如果是最后的数据块在辅助函数中需要特别留意。这是因为，最后的数据块通知，必须通过两个filter反过来推动。有了chain工厂就很容易执行Quoted-Printable的转换，如上面的例子所示。 3 Sources, sinks, and pumps
正如我们在前言介绍中所说，到目前为止，我们介绍的filters的功能就像是一个在传输网络内部的节点。数据从一个节点流过另一个节点（或者更准确的说是从一个filter流入另一个filter），最终流出。把filters链接在一起就是把节点连接成网络。但是最终的节点呢？在网络的开始，我们也需要一个用于提供数据源的节点。在网络末端我们需要一个节点获得数据，这就是sink。 Sources
让我们从2个简单的soruce开始。第一个是空source：他简单的返回空数据，可能返回一个错误消息。第二个是文件source，以一块一块数据块的方式从一个文件中产生数据，结束时关闭文件句柄。 function source.empty(err) return function() return nil, err end end
function source.file(handle, io_err) if handle then
return function()
5