Archive for the ‘软件开发’ Category

Simulation 与 Infinite-Stream

2013/03/02

SICP 确实是本博大精深的书。读过前三章,即便不能领会作者的全部意图,单就其中几个例子也是值得借鉴的。第 3.3.5 节的「约束系统」就是一种我此前并不了解的用 imperative 方式实现 declarative kownledge 的初级方案。第 3.3.4 节的「电路模拟」系统则介绍了如何用「显式 schedule」方式模拟随时间变化的系统。

读到第 3.5.2 节的 infinite-stream 时,跟上作者的思路已略显吃力。以往对递归的理解包含三个要素:终止条件、调用自身、每次调用时减小问题的规模。Inifite-stream 则不同:没有终止条件、每次调用自身时问题规模保持不变、on-demand 解决问题中必要的部分而延迟其余部分。从 3.5.3 节开始,延迟解决的部分甚至不再是直接构建 lambda 函数而是调用 stream 本身。

SICP 的这个部分似乎体现了技术书籍的一个常见问题,即便经典也不例外 —— 作者认为显而易见而略过的东西耗费了读者大量脑力。如下图:

上图 (Figure 3.25) 是第 3.3.4 节对电路系统的示意图,下图 (Figure 3.32) 是第 3.5.3 节对 infinite-stream 的信号处理示意图 (该图的例子是对 input 的积分)。近似的表现形式让我对 Figure 3.32 的意义完全迷惑,因为 infinite-stream 并没有电路模拟那样的 schedule 机制,但具有自反馈和延迟求值。通过不时对 Figure 3.32 发呆,终于在一周后恍然大悟,这两个看似差不多的系统有完全相反的性质。Figure 3.25 的系统是「输入驱动」,系统的动作由左向右进行。而 Figure 3.32 是「输出牵引」,整个系统的动作从右向左引发。输出端像一个 signal puller,每当「需要」一个信号的时候,才会激发必要的输入端提供数值。

阅读 SICP 的另一个难点也是它强大之处。Peter Norvig 在 Amazon 上对此书的评价写道 (斜体为我划出):

But … you’re not looking for one more trick, rather you’re looking for a way of synthesizing what you already know, and building a rich framework onto which you can add new learning over a career.

SICP 是一个 framework。软件开发经验不多的人很难读懂,经验足够丰富的人则面临另一项挑战:如何把已知的东西归结到这个 framework 上。为了让 framework 尽可能通用和严密,SICP 用一些更形式化的词来替代软件业常用的「行话」。读者必须自己体会这些「奇怪」名词和日常所见的联系。例如高级动态语言中经常提及的「lexical scope」在 SICP 中只出现过两次 —— 前言中一笔带过,之后出现在很晚的章节。对 lexical scope 的详细阐述以「environment model」的名称在第 3.2 节中出现。

另一个最初难以理解,但和日常所见联系起来之后就显而易见的概念是 explicit-delay。在第 3.5.4 节中提出了一个解微分方程的 stream/signal-processing 系统,如下图所示。

其中 map 和 integral 的定义相互依赖 (上图的 code 片段中,integral 函数的 delayed-integrand 的传入实参就是 map 函数),所以 integral 中依赖 map 的参数必须设计为延迟取值。听起来很玄,不过你只要把「延迟求值」设想为 pass-by-reference (即传入的不是 map 函数的指针而是函数指针的地址,因为这个函数指针在 integral 被调用之后才被赋予合法值),把 force 想像成 dereference (也就是 C 里著名的 * 操作符) 就一目了然了。这与 C 语言里定义相互依赖的类型时用指针来代替实际类型没有本质区别。

读 SICP 的有两种可能的后果。一种是扩展了你的 mindset,而另一种可能是同事们从此听你在说一种别人完全不懂的语言 (也许从你在 SICP 上看到第一行 Lisp 代码的时候就就注定了这种结果)。

Programming in Lua(四)- Nil 和 List

2012/12/22

粗浅地看,Lua 的 nil 很容易被等同于「无」。如下面这段代码:

function r_nil()
    return nil
end

function r()
    return
end

a = r_nil()
b = r()

print(a .. ", " .. b)  -->  nil, nil

尽管函数 r_nil()r() 的返回语句分别带有和不带有 nil,接受它们返回值的变量 ab 的值都是 nil。另一个例子是 nil 对 table 的作用。

tab_v = { attr1 = 1, attr2 = 2 }
for k,v in pairs(tab_v) do
    print(k .. ", " .. v)
end  -->  attr1, 1
     -->  attr2, 2

tab_v.attr1 = nil
for k,v in pairs(tab_v) do
    print(k .. ", " .. v)
end  -->  attr2, 2

将 table 的一个 field 赋值为 nil 不仅仅改变其值,而是让这个 field 本身消失了 (这个例子中是 field attr1)。

分析 nil 的实际含义可以从 Lua 的另一个比较特殊的概念 —— list 入手。List 的特殊性在于它不是 first-class 类型。「First-class」是动态语言中常被提及的概念。编程语言有越多的构成元素符合 first-class 标准,其概念模型就越一致、越简单。Lua 的基本数据类型 (包括 nil) 和函数都符合 first-class。满足 first-class 标准通常有四个要求:

  • 可以被赋值给变量;
  • 可以作为参数;
  • 可以作为返回值;
  • 可以作为数据结构的构成部分。( 注意 nil 并不完全符合这个要求,但是可以通过某个 field 的缺失来表示 nil。)

在《Programming in Lua, 2ed》的第 5.1 节提到 list 只能用于四种情形:

These lists appear in four constructions in Lua: multiple assignments, arguments to function calls, table constructors, and return statements.

List 有两种具体的表现形式,一种是用逗号分割的一组表达式,表示一个具体长度的 list;另一种是三个点构成的省略号 (...),表示其长度和内容不定。第二种表示方式不能用在 multiple assignments 的等号左方,也不能创建新 list,只能从函数的形式参数列表中获得。由此可以看出,list 不符合 first-class 标准:

  • 它的部分内容可以赋给几个变量,但本身不能作为整体赋给变量;
  • 它是参数列表的全部或一部分,但不是任何参数 (注意两者的区别);
  • 它不能作为数据结构的构成部分。注意,「...」不能作为 closure 的 upvalue。用 first-class function 存储 list 的方式行不通。

作为非 first-class 类型,list 无法被生命周期较长的数据结构存储。短期的完整传递 list 的内容只能利用函数调用/返回的方式:

function f_outer(...) -- important: f_out() must accept
                      -- "...".
end

f_outer(f_inner())
-- pass the list returned by f_inner() to
-- f_outer() as the latter's argument list

f_outer(1, 2, f_inner())
-- pass f_outer() a new list, which is "1, 2" appended
-- by f_inner()'s returned list

function f_caller(...)
   f_callee(...) -- pass argument list of f_caller()
                 -- to f_callee()

   return f()    -- pass list returned by f() to one
                 -- level up
end

另外还有一些反例:

function f_caller(...)
   a, b = ...   -- not pass a list, "a, b" is
                -- a different list of two elements
                -- obtained by adjusting the "...",
                -- and this list is very short-live,
                -- existing in this line only

   tab = {...}  -- not pass a list, tab won't
                -- have fields for nils in the "..."

   local function test(a, b)
   end
   test(...)    -- not pass a list, test()'s
                -- argument list accepts only the first
                -- two items of "..."

   for i in ... do  -- the "for" uses only the first
                    -- three elements in "..."
                    -- (two accepted by for internally,
                    -- and one received by i)
   end
end

List 会成为 Lua 中为数不多的非 first-class 类型是因为它实际代表了 stack 上的一段数据。一般只有动态分配的数据能作为 first-class 类型,操纵 stack 上的数据则只能通过函数调用的参数和返回值等有限的方式进行 (这也是因为 stack 在一定程度上代表了程序的 continuation)。不过在其它语言中,stack 的内容并没有被抽象为类似 list 这样可以被操作 (尽管不能像 first-class 类型那样自由地操作) 的概念。因为 Lua 提供了多返回值,鼓励可变参数以及参数/返回值和 table 的互相转化,特别是它著名的 C 接口就以 stack 为中心来设计,所以它有了独特的 list 概念来操作 stack。

如果在 Lua 中一定要将 list 和 first-class 混用怎么办呢?比如说,一个函数返回的 list 通常还是要存储在变量中,或者应用在某个表达式中。这是上面的反例代码中已经提及的机制 —— adjustment。Adjustment 并不是真的传递一个 list 的内容,而是用一个 list 的内容构建另一个新的 list。当新 list 的长度小于原 list,多余的值被丢弃,当新 list 长度大于原 list,就用 nil 补齐。

Lua 的 nil 担当了三种角色:

  • 一般的数据类型,通常标志某种特殊情况 (应用或算法本身的特殊情况,而非语言的特殊情况)。
  • Table field 的删除器。
  • List adjustment 的补全值。

Lua 的 nil 不代表「无」,反而恰恰起到了「有」的作用。在应用 adjustment 的情况下,我们往往用新 list 末尾的 nil 来判断原 list 的「无」。这个做法有一个缺陷:无法辩别原 list 末尾本来就确实含有的 nil。如果需要区别对待 list 结束和 list 本身含有 nil 这两种情况,既可以自行编写 C 代码来检测 stack,也可以使用 Lua 现成的 API select()。回到第一个例子,稍加修改就可以区别两种情况:

function r_nil()
    return nil
end

function r()
    return
end

a = select("#", r_nil())
b = select("#", r())

print(a .. ", " .. b)  -->  1, 0

下面是精确区别 list 结束的一个实际例子 —— 关于 stack 的递归终止条件。若希望一个函数对它的 argument list 中的每个参数执行 op() 操作:

function map_list(op, ...)
    if select("#", ...) == 0 then
        return
    else
        local a = ...
        return op(a), map_list(op,
                               sub_list(...))
    end
end

函数 sub_list() 返回的 list 是其接受的 argument list 去掉第一个元素。这个函数的实现如下 (如果用 C 语言来实现会更简单)。如果 op() 允许接受 nil 并且在此情况下返回有意义的值,或者 map_list() 接受的 list 在中间含有 nil,那么 map_list() 的递归终止条件就必须基于 select() 而不可以基于对 nil 的判断。

function sub_list(...)
    local list_start
    function list_start(start, ...)
        if start > select("#", ...) then
            return
        else
            return select(start, ...),
                   list_start(start + 1, ...)
        end
    end
    return list_start(2, ...)
end

List 是 Lua 中最不符合 first-class 的数据类型。但由于其不能作为变量但可以被函数的返回值构建的特性,List 反而可能是 Lua 中最纯粹的 functional programming  元素。放弃 table 而完全用 list 来编写 Lua 程序也许是把 Lua 转化为一种 FP 语言最简单的手段。

Programming in Lua(三)- Yields in C

2012/11/21

Handling Yields in C 是 Lua 5.2 的重大改进之一,最早从 blog《Lua 5.2 如何实现 C 调用中的 Continuation》了解到。这些资料围绕新 API lua_yieldklua_callk,和 lua_pcallk 来介绍这个新特性,自然有很多关于新增加的 continuation 参数的讨论。其实以 continuation 参数作为切入点介绍 yields-in-C 容易混淆问题的实质。首先回顾一下《Programming in Lua, 2ed》(中文版) 中的一段话 (第 30.1 章):

The only way for a C function to yield is when returning, so that it actually does not suspend itself, but its caller — which should be a Lua function.

这段话针对 Lua 5.1 而写,当时尚无 continuation 参数。严格地说这会误导读者。根据描述本身,可以理解为 Lua 无法在 C 代码中 yield (包括被 C 代码再次调用的第二层 Lua 代码以及之后的 stack 上更深的执行层次) 是因为无法纪录这种情况下 resume 所需的信息 —— C 代码的 stack 和 program counter。这种解释的推论是,在 C 代码即将返回 Lua 前,由于 C stack 已经恢复为调用前的状态 (可以称为「空 stack」),program counter 也处于即将进入 Lua 代码的状态,所以可以调用 lua_yield。原理上这个结论可以推广到 lua_call/lua_pcall。如果程序在 Lua 和 C  代码之间调用切换多次,整个 virtual stack 上的 Lua 部分的 stack 会被 C 代码分割成若干段。不过只要这三个 API 总是在 C 代码即将返回 Lua 前被调用,那么这些 C stack 都是空 stack,Lua VM 只需知道 C 代码在 Lua stack 段间的位置,不需要实际纪录 C stack/program counter 本身的内容。「在多于一层 C/Lua 切换的情形下 yield」应该正常工作。

问题是 Lua 5.1 不支持「在多于一层 C/Lua 切换的情形下 yield」!

根据上面的分析,这个限制并非 Lua 语言或 C API 本身的设计所固有,它是一个纯粹的 VM 实现问题。也就是说,即便 Lua 在 5.1 之后不引入 continuation 参数,保留「lua_yield (以及 lua_call/lua_pcall) 只能在即将返回到 Lua 之前调用」这个限制,也还是可以支持从 C 或者从第二层及以上的 Lua 代码中 yield。

Lua 5.2 实现了「在多于一层 C/Lua 切换的情形下 yield」,这是一个 VM 内部改进,仅仅为此并无必要引入 continuation 参数。 Continuation 参数解决的是另一个问题 ——「Lua 无法跟踪程序在 C 代码中的 stack 和 program counter」,但仍保留诸多限制:首先,它无法解决纪录 C stack 的问题,所以,仍然不允许在 C stack 上有多于一层 C 函数时调用新 API;其次,它也无法纪录 program counter,编写 C 代码时必须手工把可能发生 yield 之后的 C 代码 factor 到一个单独的 C 函数中,通过函数分割这种变通方式部分的模拟 yield 时的 program counter。由于没有真正的管理 C stack,充当 continuation 参数的 C 函数在运行中不能依赖 caller 的 C stack (实际上这个问题不大,因为它只能接受一个 lua_State 结构)。最后,仿照某些评测给 Lua 5.2 的新特性做一个「优雅 / 有待改进 / 丑陋」的总结:

优雅

实现了「在多于一层 C/Lua 切换的情形下 yield」。对于「Lua 无法跟踪程序在 C 代码中的 stack 和 program counter」这个问题的剪裁得当,既扩大了支持的应用场景,放松了对 C 代码的限制。同时避免了编程接口过分复杂化,和使用底层 C runtime 机制破坏 VM 的跨平台性。

有待改进

文档没有分别说明两个问题,混淆了 VM 内部实现的改进和 API 改变的原因。

丑陋

新 API 在 continuation 参数为 NULL 时沿袭旧 API 的限制 —— 禁止在多于一层 C/Lua 切换的情形下 yield。这是不必要的,也是混淆两个独立问题的误解最大的来源。现在,对于那些已经在「即将返回 Lua 之前」被调用的 lua_yieldk/lua_callk/lua_pcalk,也必须传入一个 no-op 的 continuation 函数。不过,Lua 5.2 的发布已经有段时日,估计这个 API 上的小问题也不会再未来更改了。

Programming in Lua(二)- 异常与错误码

2012/11/15

我不喜欢编程语言用「异常处理 (exception handling) 」的方式处理错误。从以往经历看,先有 C++ 创造了最差的异常实现 —— 没有 GC 帮助内存管理,扰乱 C 的二进制接口 (Application Binary Interface, ABI)。为了绕过这个拖累,维护 C++ 代码往往要花费双重开销来完成没有异常的语言可以免费获得的东西:code review 必须保证代码的「异常安全 (exception-safty)」[1],同时不写会抛出异常的新代码。

Java 提供了 GC,解决了安全实现异常处理最大的的先决条件。不过凡事皆 checked-exception 的方式令人毫无好感 [2]。Objective-C/Cocoa 中没有跨越 block 的异常机制,基本上采取传统的返回错误码方式,让我舒了一口气。但是接下来,Lua 通过 longjmp 实现跨函数的类似异常处理。一方面,让我怀疑 Lua 以简洁著称的设计是否在这点上采取了错误方式;另一方面,longjmp 并未实际引起麻烦,让我好奇异常处理是否也有某些价值。

异常处理和传统的返回错误码 (error code) 两种处理错误的方式是一场持久的争论。就在最近,围绕 Go 语言完全抛弃异常处理的语言特性,《Why I’m not leaving Python for Go》的作者表了极大失望。

Russ Cox 针对上文为 Go 语言进行了辩护。其中提到了 Raymond Chen 两篇旧日的 blog:

Raymond Chen 用严密的逻辑和实例说明了编写正确异常处理的代码 [3] 非常非常困难。特别要注意 (但不限于) 以下两点:

  • 正确管理资源,特别是资源的回收;
  • 关键数据的修改尽可能滞后。在中间可能抛出异常的步骤中,随时保证数据处于一致 (integral) 的合法状态。

关注第一点也许会令人假定,如果程序不涉及内存以外的资源,并有成熟的内存管理机制,就足以保证写出正确的异常处理代码。毕竟把异常处理放到 feature list 中的语言无不首先重视提供 GC 机制。由于需要根据异常的 stack unwinding 情形考虑内存回收,这些语言一般采用 root-tracing GC 而非 ref-counting [4]。但是,将资源管理局限于内存并不足以对第二条豁免,比如复杂的图结构 (graph structure),或者更常见的情形:对象需要向多个相互关联的全局表注册自身的引用。而且话说回来,「纯」内存数据操作除了内存用尽 (out of memory) 之外又有什么值得担忧的错误需要处理呢?归根结底异常处理是一个主要面向 I/O 问题的机制。

在「纯」内存无 I/O 的环境下,能体现异常处理价值的领域并不多,仅存的适用领域之一是语言虚拟机。这正是 Lua 采用 longjmp 类似异常处理的原因,主要用于类型检查和数组越界等语言虚拟机问题。而且这时处理的错误往往不是最终产品代码 (production code) 期待的行为,并不真正用来弥补错误,只是起一些辅助作用,比如揭示 bug 和收集诊断信息,防止应用完全退出,在多文档应用中让用户有机会保存其它信息,或者让应用以 reset 之后的状态接受其它请求。类似于 Go 中的 panic 机制和 Java 中的 runtime-exception (unchecked excpetion)。

GC 虽然是实现安全的异常处理机制的先决条件之一,但只是朝向最终解决问题的很小一步。因为真正能体现异常处理价值的地方是 I/O 密集程序。有哪些 I/O 机制目前可以做到「关键数据的修改尽可能滞后。在中间可能抛出异常的步骤中,随时保证数据处于一致的合法状态」呢?作为 naive 的尝试,C++ 提出了 RAII。但是很遗憾,异常安全的需求明显超出了 RAII 的能力。除了关系型数据库事务处理 (RDBMS transaction) 的二步式提交 (two-phase commit),我不知道还有什么 I/O 机制满足这个要求。也就是说,在日常需要的软件工具中包括图形化窗口化 UI,网络,打印等等常见 I/O 操作中,只有纯粹的数据库 CRUD 系统这个特殊领域适于异常处理机制。正因为如此,非数据库的 I/O API 的错误处理都应该采取返回错误码形式。特别是,以异常处理文件访问错误的 API 都是失败的设计 [5]。Java 正是被鼓吹适合数据库 CRUD 领域,所以其异常处理机制获得了一些正面评价。但是当其野心不限于此时,将仅限于数据库领域用的还不错的异常处理机制匆忙的推广到其它问题就招致了恶名。

某些系统通过异常处理或者类似异常处理的机制来解决某些问题,而且解决得还不错。这是它们的设计者针对一些能体现异常处理价值的特定领域选择的方案。这些成功案例并不能简单地推广。保守地说,要采用异常处理,必须保证所有资源置于二步式提交的事务管理之下;或者限于虚拟机内部对类型检查等非 I/O 操作的「粗粒度」错误处理。「粗粒度」表示一旦发生错误,系统采取的应对策略是放弃整个粒度较大的操作,异常处理仅仅保证程序不退出,收集 bug 诊断信息,或者保留机会处理其它请求,而不是去弥补刚发生的错误。特别是对于 Lua,这个问题还有一层含义。Lua 允许用 C 编写扩展。这种情况下要把基于 longjmp 的异常处理部分限于开始的参数类型检查,置于触及关键数据和 I/O 操作之前,一旦 C 代码涉及了实质的数据和 I/O 操作,错误处理方式就必须变为返回错误码机制。Lua 支持多返回值特性正是为返回错误码方式的应用提供便利。显然,Lua 的可扩展性也是其基于 longjmp 的机制彰显天下的原因,对于 Java 来说,虚拟机内部的具体实现和使用它的程序员是毫不相关的。

脚注:

  1. C++ 中所谓的「异常安全」也不过就是尽量使用 on-stack 对象 (以及基于 on-stack 对象的「智能」指针) 和 RAII (下文还有涉及) 而已。
  2. 错误处理有经常被人混淆的两个方面。一是如何保证程序员不忽略可能的错误;二是在程序员意识到可能的错误时,如何编写正确的处理代码。本文只讨论第二个方面。因为,如何「不忽略可能的错误」属于程序员掌控应用逻辑的问题,已经超出了编程语言的能力。Java 的 checked-exception 试图用语言解决这个问题,但是即便是 checked-exception,也允许程序员相当容易的把异常遗留给上层 caller。其结果是,越多的错误集中在一处处理,而且远离错误发生的地点,这段异常处理代码的正确性就越难保证 (或者这段代码除了 crash/quit 无法做任何其它有意义的工作)。也许,这正是没有任何其它语言借鉴 checked-exception 机制的原因。
  3. 注意这里的「异常处理的代码」指程序员用具备异常处理机制的语言编写处理实际错误的代码,不要和异常机制本身的实现混淆。
  4. Objective-C/Cocoa 舍弃异常处理的可能原因之一。另一方面,如果在 stack unwinding 时进行特定的处理,也可以用 ref-counting GC 配合异常。比如 C++ 调用 destructor 以及由此衍生的「智能」指针,还有 Python 的机制。但是我不喜欢这种将 unwinding 复杂化的机制。
  5. 导致每行一个 try-catch block。

Programming in Lua(一)

2012/10/21

最近没有腾出精力写 blog,不过在软件方面投入的时间并不少。决定从头到尾读完《 Programming in Lua, 2ed 》的计划目前进展平稳,没有像前几次那样半途而废。也许是开始时下决心做的投资起了些作用 —— 买了这本书的多格式电子版并将 mobi 格式放到 kindle 上。最初手中有这本书的一个来路不明的 PDF 版,再下决心买另一种格式,而且价格并不便宜,不管怎么说也感觉有些浪费。不过总归这次的进展比之前的几次成功。

Kindle 的笔记功能其实很烂,特别是既无键盘又不支持 touch 的 kindle 4。但是关键在于笔记和进度都能在一个地方集中管理,减轻了负担,至少从心理上来说是个自以为减轻了管理负担的积极暗示。当然,最初不能善用 PDF viewer 的笔记功能是我的不足,不过作为一个主要用 kindle 阅读的人,多用一个系统来管理信息看来是很大的精神负担。

另一个问题是,写了十多年软件之后,很难静下心从头开始一页页读一门新语言的基础介绍材料。总想找点捷径。这样的捷径并非绝对不存在。学 C 时找到的那些基础介绍书籍都很失败,读了几页《 C Programming Luangue 》,发现前言说了不少 Unix 就没心情看下去(毕竟是 93 年,连 Windows 3.1 还没见过)。后来找到《 C 语言常见错误 》(当年没有授权的译本,今天国内出版已经不是这个名字,不过很值得怀念)。本来是有经验的 C 程序员交流使用的资料,不过拿来给有点 Basic 知识的高中生似乎也能用来从头学习 C。或者,学 Lisp 语言可以用《 Structure and Interpretation of Computer Programming 》这样夹叙夹议的书籍。所以有点小聪明的人希望了解不熟悉的技术时,总是期望能有这种即非专为初学者,又不需要太多预先基础的东西。Lua 的经典教材显然只有这本。不过《 Programming in Lua, 2ed 》这本书其实有很高信息密度和文字质量,不止是一本介绍基础语言的书。

阅读开始前碰巧读到小说《万里任禅游》里的一句话:

When you want to hurry something, that means you no longer care about it and want to get on to other things.

所以这次决定把学习 Lua 这件事搞得舒缓一些。在新的设备,新的心态,以及儿子的成长中看这本书,倒是找回一些当年本科通信专业精疲力尽的期末复习中看那些「不相干」的计算机书籍的乐趣。

关于单元测试(续)

2012/09/24

最近「知乎」上有几个关于王垠的问题,由此得知他写的《我和 Google 的故事》。最近得知他又放弃了博士学位。虽然对他的作为不是完全赞同,但是感慨他才华出众而且有勇气做想做的事情。一个匿名用户在一个问题下给出了这样的答案:

王垠是做学术的,而且是 PLT 程序编程语言领域。所以在这个领域他批评 Google 有足够多的理由。毕竟四大语言 C++, Java, Python, 和 JavaScript 在语言设计上可以吐嘈点在普通程序员里已经很多,更不用说一个此领域的博士生。而其中说到 Python,JavaScript 的语法语义分析,这本就是其研究领域的强项。

王垠为什么看不起 Test Driven ? 这个要从他的研究背景和方向就很容易理解。他在读书时候写作业,老板的要求就远超过 Test Driven。程序不但要求从输入到输出是正确,还要求程序能倒推运行,即给出输出结果,能产生所有可能的输入。王垠做的,是逻辑编程的方向,目的是通过逻辑推导演算去保证程序的正确性。为此不难理解,为什么他对测试是那么不以为然 —— 用大量测试就能保证程序逻辑正确么?

我相信王垠在形式化方法方面的成就绝非限于 toy problem。当初看到 L4 内核的正确性被形式化证明的消息也很感兴趣。但之后发现此类方法需将源代码经过某种建模转换才能带入形式化符号系统。对于实际的产品,这种转换可能过于简化。感觉在软件开发中的实际作用有限。

不过最近有关 TDD 的思考让我有了一些新想法,似乎形式化方法的实际意义并非那么「有限」。至少,相对于很多人鼓吹的 TDD 方法的根基 —— Unit Test 这种特定类型的测试,形式化方法的局限性还那么突出吗?

复杂的软件系统中一个 class 的实例化 (instantiation) 和执行通常需要调用所依赖的其它 dependent class 的代码。Class 之间的 dependency 是 Unit Test 的最大障碍之一,因为 Unit Test 需要尽量避免触及被测 class 以外的代码,特别是运行速度较慢或附带影响较复杂的代码,例如需要访问数据库或文件系统。所以 Unit Test 需要名目繁多的 dependency breaking 技术 —— 避免调用 dependent class 代码的方法。常用的 dependency breaking 技术包括 interface/implementation extraction、mock object、parameterise constructor、static setter 等等。Interface/implementation extraction 方法为 Unit Test 特地增加产品代码的继承层次。Mock object 在增加的继承层次下构建虚假的 dependent class,令其功能从测试角度模拟真实的 dependent class,同时避免访问数据库等不利于 Unit Test 的因素。

这些所谓的「技术」让我非常不舒服。因为它们触及到测试存在本质原因 —— 人们无法保证代码的正确性。在测试前根据某些假定对代码肆意地修改,等于是在宣布:我认为自己可以无需测试即猜测这段代码的这部分是正确的,可以替换为一个 mock object 而无损对其它部分的验证。实际上,软件开发者(包括测试者)根本无法通过测试以外的手段证明软件的任何一部分是正确的。Dependency breaking 本身违背测试的根本原则。

在 Robert L. Glass 的《Facts and Fallacies of Software Engineering》里,有这样一个 Fact:

Fact 33

Even if 100 percent test coverage were possible, that is not a sufficient criterion for testing. … 40 percent (of software defect emerge) from the execution of a unique combination of logic paths. They will not be caught by 100 coverage.

注意 Robert 这里指的是包括系统测试在内的各种测试。那么,可以想像在充斥 mock object 的情况下,分离测试单个函数的功能的 Unit Test 能在多大程度上保持代码的正确性。

我相信有些人已经开始准备反驳 —— 不能因为 Unit Test 的效果不够完美就否定其存在的意义。它还是能相对提高代码的质量。那么,我觉得这些评价无疑承认 Unit Test 只是一个「聊胜于无」的技术。但不要忘记这个「聊胜于无」的技术是有成本的,如果它的投入产出效率不及其它替代技术,那么连「聊胜于无」这个称号也无法胜任。上一篇《关于单元测试》提过了 SCM 和 TDD 的投入产出效率比较。这次回到王垠的研究领域。如果我们认为形式化证明存在模型过于简化这样的局限性,不妨审视一下 TDD 所鼓吹的 dependency breaking,其本质无非也是一种建模简化技术。TDD 在建模简化之后仍然需要搭建一个基本环境实际运行幸免于修改的代码来验证其正确性。而形式化方法全过程都无需搭建运行环境。似乎后者的成本更低。

以我有限的理论基础,不能像之前 SCM 和 TDD 的比较那样,对形式化方法的效率下一个比较确定的结论,也许形式化方法目前还不够用于实际的软件产品开发。即便如此,我相信形式化方法比 TDD 更有前景。因为形式化方法的一切缺陷,Unit Test 在本质上都无法避免;另一方面,鼓吹 TDD 的人丝毫不以为自己在进行着过度简化,也不认为自己鼓吹的技术有其它更有效率或者更有前景的替代物。

关于单元测试

2012/09/04

关于测试驱动开发 (Test Driven Development) 的争议之一是,耗费相当人力编写单元测试代码能否真的带来开发效率的净收益。

TDD 的拥趸认为答案是肯定的:完备的单元测试可以极大缩短从代码修改到发现错误的 turn-around 时间,在理想情况下,每次修改后仅需几分钟的单元测试可以立即发现并定位错误,修复错误并保证代码质量的开销得以降低。他们抱怨在缺乏单元测试的情况下,即使测试团队积极参与,从代码修改提交到发现问题通常也会经过几天时间。如果测试团队仅运行系统功能测试而缺乏模块级别测试,发现问题甚至可能推迟到几周之后。TDD 拥趸认为如此长的 turn-around 时间必然极大地增加定位错误的困难。当然,TDD 的拥趸也承认接近理想的单元测试并不轻松,除去编写和维护一套并行于产品代码并且需要和产品代码同时演进的测试代码的工作量,还必须用 extract interface/implementation 、parameterize constructor 、mock object 等对代码清晰度构成干扰的 dependency break 手段改造产品代码。

几乎所有我熟悉的同事,包括我自己都对单元测试有诸多怀疑。切身感受告诉我们,TDD 的鼓吹者似乎遗漏了某些环节。比如说有这么一项技术,它本身远非完美,需要程序员花费一定精力来掌握和操作,但是消耗的精力低于 TDD,对产品代码清晰度的干扰也低于 TDD,又能保证和 TDD 相当的代码质量。从推行 TDD 耗费的精力来看,存在一种投入产出更有效率的技术的可能性并不是悲观的。

最近我似乎找到了这项技术。TDD 的拥趸很少提及版本管理系统 (Source Control Management System, SCM 系统) 的作用。我不是说那些鼓吹 TDD 的人都不会用 SCM,但是他们似乎没有意识到 SCM 的关键作用。而像我们这样的人又往往认为 SCM 在软件开发中的核心地位透明得像空气一样,以至于在讨论中疏于提及 SCM,想当然地认为他人不至于忽视这个技术。但是 TDD 拥趸的各种论述似乎说明他们对 SCM 的认识远远低于我们的想象。

SCM 鼓励程序员采用一种大胆尝试的态度进行开发。现代的分布式 SCM 系统 (DSCM) 提供低开销的 branching 功能,鼓励为目的单一的短小修改创建 submission,而非为整个 feature 构建巨大的单个版本。Braching 和维护多个短小修改并非没有开销,但是相对来远低于 TDD。实践这些版本管理策略让 code base 成为一组可以单独 revoke 的 submission 序列 (或者说一组序列,因为 branching 还为 revokability 的粒度提供进一步的层次管理) 。Revoke 较早提交的 submission 通常并不会干扰较晚提交的 submission。这正是 TDD 的拥护者在鼓吹他们的技术时所忽视的另一种保证质量的方式,他们把 code base 看成是一个冰激凌蛋筒,先放进去的冰球被后放进去的死死压住。所以在放每一个冰球的时候都要异常小心地舔两口来保证质量。更糟糕的是,全面单元测试容易鼓励一种习惯:既然每次修改由单元测试保证正确,小的修改就不必进入 SCM 系统成为单独 submission,只有完整的 feature 才被提交到 SCM 系统。甚至可以怀疑 TDD 正是 Subversion 统治 SCM 的黑暗中世纪诞生的极端思想。

而我们这类人希望把 TDD 所消耗的精力节省下来用于让 SCM 发挥最大的作用。保证每一次 submission 尽量短小并互不干扰。保证每次 submission 之后的 code base 都处于一个基本 deliverable 的状态,让 experimental branch 和 main branch 的距离恰当的体现代码的成熟度。固然这也需要相当的技巧和努力,它对产品代码清晰度产生的是正面促进而非干扰,无需平行地维护一套产品之外的测试代码。SCM 令 design for testability 让位于 design for clarity。

在 SCM 应用良好的项目中,从代码修改到发现 bug 的 turn-around 时间可能会有所增加,但不会增加定位问题的难度。在中等团队中,turn-around 时间的增加只是在吞吐量 (through-put) 和反应度 (responsiveness) 之间的自然取舍,并无实质资源的浪费。基于 SCM 的产品更像操作系统的 page fault 机制,可以而且仅在真正出现问题的地方投入资源。退一步说,在真正出现问题的地方,SCM 可以赋予开发者在局部采用 TDD 模式的自由。如果在正常情况下一种模式比另一种模式开销低,而且前者可以在异常情况下无缝切换到后者,那么后者根本不值得作为常态的工作方式。

人类预测未来的能力非常糟糕,工具的发展趋势是帮助人们把分配资源的决定尽量推迟到必须做决定不可的时候。那种寄希望于预先精细计划并分配资源来保证正确性的 wishful thinking,就像「瀑布模型」和「premature optimization」,必须被更灵活的决策机制取代。

Core Animation 初探

2012/08/17

尽管在产品中要实现不少动画效果,却还没用过 OS X 的 Core Animation。一方面是因为经常要考虑用一套 code base 兼顾 OS X 和 Windows 两个操作系统。另一方面是习惯了基于 MVC 的手工实现方法 —— 在 model 中加入描述过渡帧的变量,用 timer 定期修改变量并通知 view,view 根据变量绘制过渡帧。不过偶尔模糊地见闻一些对 Core Animation 的褒扬 —— 充分的利用 GPU,释放主线程的压力,iOS 的 graphics 完全转向 Core Animation 等等。所以最近终于抽空看了些 Core Animation 的资料 [1]。

真正阅读资料之前对简介 Core Animation 的优点一直有些疑问。我无法设想与手工 MVC 动画相比 Core Animation 如何进一步压榨 GPU 的效能。在手工 MVC 动画中,虽然控制中间过程的变量需要 CPU 计算,但是这种变量会被设计为最简形式。比如,实现旋转一个矩形的动画时 timer 修改的不会是矩形的四个顶点,而是在 model 中存储旋转角度的变量。在 view 绘制中间帧时,才会根据这个角度计算四个顶点。这时的计算并非主要由 CPU 承担,而是把旋转角度变为旋转矩阵,交给 GPU 担负各个顶点的计算。

Core Animation 文档再次印证了我的一个感觉。当你感觉一个东西表面上被宣称的优点不成立,那么这种感觉很可能是对的。如果这个东西仍然很流行,那么在宣传中肯定遗漏了这个东西的真正优点 [2],并且伴随着一些隐晦的妥协 [3]。Core Animation 的妥协在于,它并不能完全替代手工 MVC 方式的灵活性。手工 MVC 动画中 model 里描述过渡状态的变量和 view 根据这些变量计算显示过渡帧的过程可以自由定义,在 MVC 这一套原则下可以实现任何动画。Core Animation 仅仅实现了有限的预定义动画,如 layer 的旋转,透明度变化,颜色,位移。尽管 Core Animiation 预定义的动画属性相当多,而且有数种组合方式达到无限的组合结果,但是仍然不能覆盖理论上的任何动画。所以它的动画效果是「罐装 (canned)」的。

但「罐装」效果对灵活性的牺牲带来了在表面宣传中未提及的好处 —— transactional。即使是初学者也能很快的实现一个简单的手工 MVC 动画,但是一旦加入复杂的 transaction 要求,即使老手也很为难:如何处理在一个动画播放的过程中用户 cancel 或者 undo 一个操作,或者更加复杂,在动画过程中用户执行引发另一个动画的操作。这要求动画在任意阶段的回退,或者从一个动画效果无缝切换到另一个效果,并保证 view 最终总能正确呈现 model 的稳定状态。通过把动画效果限制在有限的「罐装」组合,Core Animation 在程序员无需干预的情况下自动实现 transaction [4]。

更重要的是,虽然理论上听起来「罐装」效果对灵活性的牺牲很可怕,实际上 99% 的应用只需要「罐装」效果,因此 Core Animation 作出的牺牲其实是几乎无代价的。当然,不排除由于 Core Animation 的流行,一些原本应该更有创意的动画的地方被用平庸的「罐装」效果来应付。但我认为这是很罕见的情形。而且,动画效果已经从早期的 eye candy  变成提供 UI 行为的 clueness 的普遍要素(比如,当前的 view 变化是因为图像旋转还是图像发生了变化 —— 前者显示为图像旋转而后者则是新旧图片的平移切换)。从少数 fancy 操作扩展到几乎所有 view 的变化。动画的一致性 (consistency) 和 least suprise 变得比创意更为重要。

如果抛开 Core Animation 出现的真实历史 (historical accuracy) 来设想一下一个类似 Core Animation 的库是如何在 Apple 这样的公司出现的。它应该不会是自上而下的需求,不会是为了 OS X 的市场而设计的 feature。相反,像 Apple 这样的公司会对内部产品的界面动画有一套详尽的关注细节的指导原则,最初必然是由程序员用手工 MVC 实现,只需要极少创意和极复杂的 transaction 处理。于是一段时间之后程序员们终于把动画效果「罐装」起来,此后原来的指导原则也几乎不再有提及的必要,因为几行代码就能自然地实现,反而是没有动画效果的操作显得不够自然了。这必然是从真实的痛苦中诞生的技术。

脚注:

  1. 看的是 OS X 版本,所以对 iOS 平台的描述仍然不尽明了。
  2. 比如很多场合人们宣称 GPU 的优势在于大规模并行。这当然会引来一些思维敏捷的初学者的疑问 —— 为什么 Intel 们不把 CPU 做得一样并行化。而 GPU 的威力真正来源是它把要处理的数据结构局限在异常简单而且可以完美对齐的方式,并且配以高速的内存总线。最直接的证据就是无论 OpenGL 还是 OpenCL,在可预见的未来都不会支持指针。
  3. 如上 GPU 对数据结构的妥协。
  4. 底层实现上,Core Animation 通过三套 layer tree 实现自己的 MVC 结构来实现 transaction。这同样是由于把问题局限于「罐装」效果才可能做到。Core Animation 自己的 mini-MVC 让 app 的 MVC 架构脱离了动画 transactional 的负担。

开发 Batch Crop

2012/07/16

从 6 月 8 日到今天有一个多月没更新 blog,以前从未拖过这么久。因为这段时间在开发我的第一个准备在 Mac App Store 上发布的应用 —— Batch Crop。前几天终于把 1.0 版提交给 Apple iTunes connect 等待审查(就我的习惯来说,这个应用应该叫 0.6 版,但是 Apple 不允许 beta 版进入 App Store)。目前页面中的截图是正在开发的新版本。

以前作为 one man team 开发软件的经历不是很多。这次经历感受匪浅,想写的东西也不少。无奈不断改进 Batch Crop 的工作完全占用了 day-job 和家庭之外的所有时间。这也让我开始非常敬佩那些既开发自己的产品又撰写 blog 的牛人们。

Text Field 与 Field Editor

2012/06/08

Cocoa 提供了两种文本编辑控件 [1]:NSTextViewNSTextField。从表面上看,前者比后者功能丰富,前者一般用作复杂的文字编辑,后者一般接受简单的数据输入。二者处理 Enter 和 Tab 键的行为不同。NSTextView 的方式和通常的编辑器相同:给编辑内容添加换行或者 tab 字符。
NSTextField 的方式则类似于其它非文本编辑的 Cocoa 控件:Enter 键触发 target action(缺省为终止编辑),Tab 键令焦点移到相邻的下一控件。

有瑕疵的世界观

如果根据表面现象粗浅地猜测,有这么几种可能:

  • 二者是实现完全不同的类,运行时没有协作;
  • NSTextView 是 NSTextField 的子类;
  • NSTextField 是 NSTextView 的封装,对外隐藏后者的高级功能。

实际上这三个猜测都是错误的。查看文档可以排除第二种。另外两种的真伪则要花些功夫来辩明。当然,很多应用界面仅需要 NSTextView 提供的缺省 rich-text 编辑功能以及把 NSTextField 作为简短数据输入方式,所以我们大可以采用第一种假设来开发 90% 的应用。但若需要精细调整文本编辑行为,采用有瑕疵的猜想像是用牛顿力学和以太的概念指导宇宙航行。

以太概念的抛弃

要了解两个类的关系,它们的命名可以作为切入点——其中的「field」是什么意思?在数据库记录、表格或文件格式中一段相对独立的数据经常被称为「field」,所以自然的猜想是 NSTextField 作为简单的数据输入方式其名称中的「field」源于此意。但是 field 还有「现场」、「场所」的意思。

其实在 Cocoa 中提供文本编辑功能的类只有 NSTextView
NSTextField 不是 NSTextView 的封装,它的作用是为实际承担编辑工作的 NSTextView 提供操作「场所」。其名称中「field」的意义不是表格或文件格式意义上的 field。当一个 NSTextField 控件不拥有焦点的时候,它只显示自己存储的文本值 [2],并不和 NSTextView 有任何关系。当它获得焦点时,其所在的窗口会把一个 NSTextView 控件置于其上,并将原来的 NSTextField 对象设置为该 NSTextView 对象的 delegate,真正获取焦点并且成为 first responder 的控件是 NSTextView 对象。在同一窗口中,置于所有 NSTextField 之上的是同一个 NSTextView 对象实例。因为只有一个控件能获得焦点,所以共享单一的 NSTextView 实例没有问题。这个唯一的实例称为「field editor」,即放置在 text field 上的 editor。

Field editor 由窗口负责创建和管理。开发者如果希望实现自己的 field editor,可以重写 (overried 或者 implement) 下面的函数之一:

  • NSWindowfieldEditor:forObject:
  • 窗口的 delegate 的 windowWillReturnFieldEditor:toObject:

在说明 field editor 机制如何导致对 Enter/Tab 的不同处理行为之前,先简单说明一下 Cocoa 对键盘事件的总体处理机制。下图截自《Cocoa Event Handling Guide》,Figure 1-5。

最后一步「Insert as character in view」对于 NSTextView 来说相当于接收到 keyDown: 消息。Enter/Tab 作为 key action 被路径中更早的模块截取 [3],即图中的「Send action message to first responder」。所以 Enter/Tab 事件不会向 field editor 发送 keyDown: 消息,而是分别发送 insertNewLine:insertTab: 消息。

现在回到 NSTextViewNSTextField 对 Enter/Tab 的不同处理。严格的说是非 field editor 的 NSTextView 对象和作为 field editor 的 NSTextView 对象的不同行为。 NSTextView 的 isFieldEditor 属性表示当前对象是否为 field editor。一切行为差异的秘密就在于 insertNewLine: 和 insertTab: 会根据 isFieldEditor 的返回值来决定控件的行为。

问题的解决

有了正确的世界观,就可以自由地对文本编辑行为作出调整。比如,如何让控件在接收到 Enter/Tab 事件的时候始终插入相应的字符而非终止编辑或者切换焦点?可以有以下方案:

  • 始终用 NSTextView,并且保证 isFieldEditor 属性返回 NO
  • 重写窗口 delegate 的
    windowWillReturnFieldEditor:toObject: ,返回 custom field editor。此方案需要创建两个新类:窗口 delegate 和 NSTextView 的子类。后者的 insertNewLine: 和 insertTab: 需要被改写。
  • 让处理 key action 的模块发送 insertNewLineIgnoringFieldEditor: 和
    insertTabIgnoringFieldEditor: 消息给 field editor,保证始终插入换行或 tab 字符。

下面详细说一下如何实现最后一个方案。处理 key action 的模块首先检查拥有焦点的 NSTextField 是否有 delegate。如果有的话会向其发送 control:textView:doCommandBySelector: 消息。重写此函数可以改变发送到 field editor 的消息 [4] [5]。

- (BOOL)control:(NSControl*)control textView:(NSTextView*)fieldEditor
                         doCommandBySelector:(SEL)commandSelector
{
    if (commandSelector == @selector(insertNewline:)) {
        [fieldEditor insertNewlineIgnoringFieldEditor:self];
        return YES;
    } else if (commandSelector == @selector(insertTab:)) {
        [fieldEditor insertTabIgnoringFieldEditor:self];
        return YES;
    }
    return NO;
}

脚注:

  1. 本文混用「控件」和「类」来表示 NSView 的子类。在强调该类的用户界面交互行为的时候偏向于使用「控件」。
  2. 实际上 Cocoa 中的静态 label 也是由 NSTextField 实现,只不过这时它没有获取焦点的能力,不作为 NSTextView 的「field」。
  3.  这个「更早的模块」是 Cocoa 的 key-binding manager。可以参见《Cocoa Event Handling Guide》的 Key Bindings 章节等。
  4. 用 debugger 在其中设置断点查看 call-stack 可以发现更多信息,比如关于 key-binding manager 的信息。
  5. 更多细节可以阅读《Editing Programming Guide》的 Working With Field Editor,以及《Technical Q&A 1454》。