/blog/ekd123

SICP 1.1 节「程序设计的基本元素」给出了一个计算平方根的算法，原书并没有给出证明，大概是因为不太适合书的主题，我在此写这个证明只是为了补充书上所缺，满足自己的强迫症，如有错误请指出！

证明

数学表达如下：

对于任意实数 [tex]b>0[/tex]，数列 [tex]a_n[/tex] 的递推公式是 [tex]a_{n+1}=\frac{a_{n}+b/a_{n}}{2}[/tex]，且[tex]a_1=1[/tex]，那么当 n 充分大时，[tex]a_n[/tex] 可以无限接近 [tex]\sqrt{b}[/tex]。下面给出证明。

由 [tex]a_{n+1}-a_{n}=\frac{b-a_n^2}{2a_n}[/tex] 可知，当 [tex]a_n<\sqrt{b}[/tex] 时，数列 [tex]a_n[/tex] 是严格递增的；当 [tex]a_n>\sqrt{b}[/tex] 时，数列 [tex]a_n[/tex] 是严格递减的。容易知道，当 b > 1 时，数列 [tex]a_n[/tex] 严格递增且有上界；当 b = 1 时，无疑 [tex]a_n=1[/tex] 恒成立；当 b < 1 时，数列 [tex]a_n[/tex] 严格递减且有下界。因此确信数列 [tex]a_n[/tex] 收敛且存在极限，记作 [tex]a[/tex]。

递推式两边取极限得：[tex]a=\frac{a+\frac{b}{a}}{2}[/tex]

整理即得：[tex]a=\sqrt{b}[/tex]

也就是，当 n 充分大时，[tex]a_n[/tex] 可以无限接近 [tex]\sqrt{b}[/tex]。

注记

我一开始认为 [tex]a_1[/tex] 是可以选取任意正数的，后来计算一番发现，存在特定的组合 [tex]a_1[/tex] 和 [tex]b[/tex]，使得数列不收敛。如当 [tex]{a_1}^2=\frac{\sqrt{2}+1}{3}b[/tex] 时，[tex]a_3 = a_1[/tex]，此时所有奇数项相等，所有偶数项相等，数列围绕 [tex]\sqrt{b}[/tex] 摆动而不收敛。尽管在计算机上存在浮点数舍入误差，不一定能产生预期的效果，但是只有当[tex]a_1=1[/tex]时才能在数学上严格证明出对于所有正数 [tex]b[/tex] 都一定能求出算数平方根的近似值。

实际上迭代算平方根的方法很多，比如说还可以由 [tex]c^2-1=b-1[/tex] 得到 [tex]c_{n+1}=\frac{b-1}{c_n+1}+1[/tex]，可以证明该数列的极限也是 [tex]\sqrt{b}[/tex]（选取恰当的 [tex]c_1[/tex]）。在此不再赘述。

之前有人问到如何从 C 端访问 Tcl 变量，此处做一总结。庶几不失「现代」之名。有关 Tcl_Obj 的维护者资料击此。

于是终于回到了主线。《Tcl 现代方法》本来是作为记录 Tcl 现代用法的系列博文，一开始是介绍 C 库的，但是后来 Tcl 脚本的内容反倒更多，结果现在纯粹谈起来 C 库又会导致歧义，因此在标题前加上 lib 标记，以示内容是 C 库而非 Tcl 脚本。

本文是从底向上逐步构建其 TclOO 大框架的，如果你更喜欢自顶向上的，可以参考别的教程。

另外，本文只是入门级别，读完本文后再去看文档或者其他教程应该会容易些，毕竟是汉语写的。这里我推荐 Ashok 写的《Tcl Programming for Windows》中的 TclOO 一章。

除去协程，面向对象编程也是现代编程语言不可或缺的一部分。Tcl 在 8.6 之前都没有内建支持面向对象编程，但这不意味着 Tcl 没法 OO——恰恰相反，Tcl 有一大堆 OO 库，我随口就能叫出几个出名的：[incr Tcl]、XOTcl、Snit。这些库各有千秋，有的模仿 C++，有的是原型继承，还有的是模仿 Common Lisp Object System，千姿百态。可能和大家所想不同，这样的「大好」局势并未给 Tcl 带来许多好处：依然有人批评 Tcl 没有 OO 支持；有的人虽然知道有，但批评选择太多让用户无所适从，或者为自己所爱的库口诛笔伐；有的人虽然不在乎别人怎么选择，但很苦恼其他扩展包依赖了自己根本不需要的 OO 库……在这种情况下，Tcl Core Team 站了出来，提出了 TIP 257，由 Donal K. Fellows 主要实现。这套面向对象机制起名叫做 TclOO，并随 Tcl 本身提供。TclOO 的设计十分灵活，可以以此为基础重新制作 [incr Tcl] 等库，让大家其乐融融地生活在一起。

思考一下，开源系统的桌面环境是不是也是这样呢？

协程已经是现代语言的必备要素了。Tcl 的协程仿效的是 Lua，在 8.6 版本中引入。（感谢 NRE 引擎！）

TclHttpd 是 Tcl 界人尽皆知的有名软件，功能强大，易于使用。在其原作者不再维护之后，Cliff 和 Sean 于最近接手维护，使之支持最新的 8.6。

Tailcall 是 Tcl 8.6 引入的新功能。功能如其名，本来是用来实现尾调用的。

#include <tcl.h>

/**
 * puts [set a [expr {20 * 30}]
 */
void EvalString(Tcl_Interp *interp) {
    Tcl_Obj *result;
    char script[] = "set a [expr {20 * 30}]";
    
    if (Tcl_Eval(interp, script) != TCL_OK) {
        fprintf(stderr, "Error was: %s\n", Tcl_GetStringResult(interp));
        return;
    }
    result = Tcl_GetObjResult(interp);
    printf("%s\n", Tcl_GetStringFromObj(result, NULL));
}

/**
 * puts [set a [expr {30 * 30}]]
 */
void EvalStringObj(Tcl_Interp *interp) {
    Tcl_Obj *script;
    Tcl_Obj *result;
    
    script = Tcl_NewStringObj("set a [expr {30 * 30}]", -1);
    Tcl_IncrRefCount(script);
    Tcl_EvalObjEx(interp, script, 0);
    result = Tcl_GetObjResult(interp);
    printf("%s\n", Tcl_GetStringFromObj(result, NULL));
}

/**
 * puts {hello world}
 */
void EvalListObj(Tcl_Interp *interp) {
    Tcl_Obj *cmd;
    cmd = Tcl_NewObj();
    Tcl_ListObjAppendElement(interp, cmd, Tcl_NewStringObj("puts", -1));
    Tcl_ListObjAppendElement(interp, cmd, Tcl_NewStringObj("hello world", -1));
    Tcl_IncrRefCount(cmd);
    Tcl_EvalObjEx(interp, cmd, 0);
    Tcl_DecrRefCount(cmd);
}

/**
 * puts [set a 32]
 */
void Eval(Tcl_Interp *interp) {
    int i;
    Tcl_Obj *scriptArr[3];
    Tcl_Obj *resultObj;
    int result;
    
    scriptArr[0] = Tcl_NewStringObj("set", 3);
    scriptArr[1] = Tcl_NewStringObj("a", 1);
    scriptArr[2] = Tcl_NewIntObj(32);
    for (i = 0; i < 3; ++i) {
        Tcl_IncrRefCount(scriptArr[i]);
    }
    Tcl_EvalObjv(interp, 3, scriptArr, 0);
    for (i = 0; i < 3; ++i) {
        Tcl_DecrRefCount(scriptArr[i]);
    }
    resultObj = Tcl_GetObjResult(interp);
    Tcl_IncrRefCount(resultObj);
    Tcl_GetIntFromObj(interp, resultObj, &result);
    Tcl_DecrRefCount(resultObj);
    printf("%d\n", result);
}

int main(int argc, char *argv[]) {
    Tcl_Interp *interp;
    
    interp = Tcl_CreateInterp();
    EvalString(interp);
    EvalStringObj(interp);
    EvalListObj(interp);
    Eval(interp);
    Tcl_DeleteInterp(interp);
    return 0;
}

proc lambda {vars args body} {
    set exvars [lmap var $vars {
        upvar $var localvar
        list $var $localvar
    }]
    lappend args {*}$exvars
    list apply [list $args $body]
}

简单地用 apply 实现一个“伪闭包”。其中 {*} 需要 Tcl 8.5，[lmap] 需要 8.6。

所谓“伪”是因为这个函数没法真正地持有变量引用，只能复制一下。有点像是缩水版的 C++ 闭包。虽说只是复制，但还是十分好用，因为 Tcl 在核心层面的“复制”使用的是引用计数，而且若原函数退出，也不会影响到匿名函数里面的变量，毕竟 Tcl 是没有垃圾收集的，这样做凑合能算不错吧。

有个比较遗憾的限制是，因为我比较懒，用“可选参数”实现了变量复制，所以如果参数列表有 args 且使用了外部变量，就会退化到普通的变量（正如 lambda 自身的 args）。

这个函数基本用法是这样的：

set x 100
{*}[lambda x {a b} {
    puts "x = $x\na=$a\nb=$b"
}] 10 20

自然，你也可以给 lambda 返回的“闭包”一个名字：

set x 100
set closure [lambda x {a b} {
    puts "x = $x\na=$a\nb=$b"
}]
{*}$closure 10 20

实际上，这玩意在 Tk 上最好用：

proc foo {} {
    set msg "使用 lambda 辅助函数十分方便吧！"
    ttk::button .b -text 点我 -command [lambda msg {} {
        tk_messageBox -message $msg
    }]
    pack .b
}
foo

一般情况下，Tk 直接这样写是不行的，因为 -command 是在全局命名空间里执行的：

proc foo {} {
    set msg "这是不行的！"
    ttk::button .b -text 点我 -command {
        tk_messageBox -message $msg
    }
    pack .b
}
foo

会报错找不到 msg 变量。

如果你比较熟悉 Tcl，可能想问为什么不用 subst，像下面这样：

proc foo {} {
    set msg "hello tcl!"
    ttk::button .b -text 点我 -command [subst -nocommands {
        tk_messageBox -message $msg
    }]
    pack .b
}
foo

我开始也以为可以，但遗憾的是，不行。因为 Tk 使用 eval 处理 command，在上面的例子中，eval 会把原来好好的命令曲解成这样：

tk_messageBox -message hello tcl!
# 也就是
tk_messageBox -message {*}"hello tcl!"

这是因为 eval 使用了 concat，而 concat 会把列表展开一层，正如 {*} 一样：

concat {{1 2} 3} 4
# → {1 2} 3 4

eval 的“展开”特性在少数情况下有用，大部分情况下 {*} 就可以替代 eval，在此不赘述。