Dc (程序)

dc（desk calculator：桌面计算器），是采用逆波兰表示法的跨平台可编程计算器计算器，它支持任意精度算术。它是Robert Morris在贝尔实验室工作期间书写的，作为最老的Unix实用工具，先于C语言的发明。像那个年代的其他实用工具一样，它有着一组强力的特征和简洁的语法。传统上，采用中缀表示法的bc计算器程序是在dc之上实现的。

## 历史

dc是幸存的最老的Unix语言。在贝尔实验室收到第一台PDP-11的时候，用B语言写成的dc是在这个新机器上运行的第一个语言，甚至在汇编器之前。

## 基本运算

在dc中要做4和5的乘法：

```console
$ dc
4 5 *
p
20
q
```

这可转译为：“把4和5压入栈顶，通过乘法算符，从栈中弹出两个元素，将二者相乘并把结果压回栈顶”。接着使用`p`命令打印栈顶的元素。使用`q`命令退出此次调用的dc实例。注意数值相互间必须以空白分隔，但某些算符可以不必如此。

还可以用如下命令得到这个结果：

```console
$ dc -e '4 5 * p'
20
$ echo "4 5 * p" | dc
20
$ dc -
4 5 *pq
20
$ cat <<EOF > cal.dc
4 5 *
p 
EOF
$ dc cal.dc
20
```

使用命令`k`来变更算术精度，它设置算术运算的小数位数。缺省精度是`0`，例如：

```console
$ dc -e '10946 _6765 / p'
-1
```

dc将输入数值的前导`_`识别为负号。

通过使用命令`k`调整精度，可以产生任意数目的小数数位，例如：

```console
$ dc -e '7k 10946 6765 / p'
1.6180339
```

dc中除法采用截尾函数，模除得出余数的正负号同于被除数，例如：

```console
$ dc -e '1k 10946 _6765 % p'
122.0
```

dc有科学计算器的基本运算功能：命令`^`计算整数次幂，命令`v`计算平方根。例如求黄金分割率$\frac {1 + \sqrt{5}} {2}$的值：

```console
$ dc -e '7k 1 5 v + 2 / p'
1.6180339
```

`d`命令用于复制栈顶元素。`r`命令用于对栈顶和仅次栈顶的两个元素进行对换。`z`命令用于压入当前栈深度，即执行`z`命令前栈中元素的数目。

## 输入/输出

使用`?`命令，从stdin读取一行并执行它。这允许从宏中向用户要求输入，故而此输入必须是语法上正确的，并且这有潜在的安全问题，因为dc的`!`命令可以执行任意系统命令。

前面提及过，`p`命令打印栈顶元素，带有随后的一个换行。`n`命令弹出栈顶元素并输出它，没有尾随换行。`f`命令打印整个栈，从栈顶到栈底并且一项一行。

dc还支持控制输入和输出的底数。`o`命令设置输出底数，输出底数必须大于等于2。`i`命令弹出栈顶元素并将它用作输入底数，输入底数必须在2和16之间，十六进制数字必须大写以避免和dc命令冲突。要记住输入底数将影响对后面的所有数值的分析，所以通常建议在设置输入底数之前先设置输出底数。例如将二进制先转换成十六进制再转换成十进制：

```console
$ echo '10011010101111001101111011110000' | dc -e '16o2i ? p 1010i10o p'
9ABCDEF0
2596069104
```

要读取设置的这些数值，`K`、`I`和`O`命令将压入当前精度、输入基数和输出基数到栈顶。

## 语言特征

除了上述的基本算术和栈操作，dc包括了对宏、条件和存储结果用于以后检索的支持。

### 寄存器

寄存器在dc中是有着单一字符名字的存贮位置，它可以分别通过命令`s`和`l`来存储和检索，它是宏和条件的底层机制：`sc`弹出栈顶元素并将它存储入寄存器`c`，而`lc`将寄存器`c`的值压入栈顶。例如：

```bash
3 sc 4 lc * p
```

寄存器还被当作次要栈，可以使用`S`和`L`命令在它们和主要栈之间压入和弹出数值。存储栈顶元素到寄存器中并把这个元素留在栈顶，需要联合使用`ds`命令。

### 字符串

字符串是包围在`[`和`]`之中的字符，可以被压入栈顶和存入寄存器。使用`x`命令从栈顶弹出字符串并执行它，使用`P`命令从栈顶弹出并打印字符串，无尾随换行。`a`命令可以把数值的低位字节转换成ASCII字符，或者在栈顶是字符串时把它替换为这个字符串的第一个字符。此外没有方法去建造字符串或进行字符串操纵。

`#`字符开始一个注释直到此行结束。

### 宏

通过允许寄存器和栈项目像数值一样存储字符串，从而实现了宏。一个字符串可以被打印，也可以被执行，就是说作为dc命令的序列而传递。例如可以把一个宏“加`1`并接着乘以`2`”存储到一个寄存器`M`中：

```bash
[1+ 2*]sM
```

下面的命令将一个数值`3`压入栈顶，使用`x`命令执行存储在寄存器`M`中的宏，并打印留在栈顶的结果：

```bash
3 lMx p
```

### 条件

最后提供了有条件执行宏的机制。命令`=M`将从栈顶弹出两个值，如果二者相等，则执行存储在寄存器`M`中的宏。如下命令序列将在原栈顶元素等于5的条件下打印字符串`equal`：

```c
[[equal]p]sM d 5= M
```

这里使用了`d`命令保留原栈顶元素。条件包括：`=`、`>`、`<`、`!=`、`!>`、`!<`，如果栈顶元素分别等于、大于、小于、不等于、不大于（小于等于）、不小于（大于等于）仅次于栈顶的元素，则执行指定寄存器中的宏。注意不同于Forth、PostScript和Factor，在不等式比较中的运算元的次序同在算术中的次序相反，`5``3``-`等价于中缀表示法的`5``-``3`，然而`5``3<``R`在`3<``5`时运行寄存器`R`的内容。下面是有条件执行宏的示例：

```console
$ echo 5 | dc -e '? [[equal]p]sM d5=M'
equal
$ echo 4 | dc -e '? [[equal]p]sM d5=M'
$
```

这里的宏之中有嵌入的字符串，这个命令在栈顶元素等于`5`之时有相应的输出，在它不等于`5`之时没有输出。

如果要实现一般编程语言中表达有两个分支控制流程的条件运算符`?:`或条件语句，则需要两个宏构造，例如：

```console
$ echo 5 | dc -e '? [[equal]p q]sM [d5=M [not equal]p]x'
equal
$ echo 4 | dc -e '? [[equal]p q]sM [d5=M [not equal]p]x'
not equal
```

这里的两个宏之中都有嵌入的字符串，这个命令在栈顶元素等于`5`和不等于`5`之时都有相应的输出。

`q`命令退出2层宏，如果宏少于2层则退出dc。`Q`命令从栈顶弹出一个值作为退出宏的层数，比如`2Q`命令退出2层宏，它永不导致退出dc。

## 递归示例

通过定义进行有条件的递归调用的宏，可以实现递归过程和迭代运算。

### 阶乘

下面是对栈顶元素计算阶乘$n! = n\cdot (n-1)!$的递归过程，这个过程在`x > 0`时有效，它可直接转写为互递归形式：

```bash
# F(x):
#   1 < x ? G(x) : x
# G(x):
#   x * F(x-1)
# F()
[d 1- lFx *]sG [d1<G]dsFx
```

在dc中条件算符所执行的宏必须事先存储在变量中，不支持通过嵌套的宏定义实现控制结构，故而本文中的伪代码采用了条件运算符`?:`而不采用条件语句。采用邱奇布尔值编码`if = λp.λa.λb.p a b`，定义`guard = λc.λP.λF.λx.if (P c x) (F x) x`；这里用伪代码表示为`1 < x ? G(x) : x`的，相当于`guard 1 < G`，它是高阶函数`guard`已经接受了实际参数`1`和函数参数问题`<`及`G`的部分应用，在测试条件不成立时相当于恒等函数。这里的`F(x):`是过程定义，过程`F`消费在栈顶的命名为`x`的一个值；这里的`F(x-1)`是过程调用，在调用过程`F`之前先将`x-1`的结果值压入栈顶；这里的`F()`也是过程调用，在调用过程`F`之前不需要向栈顶压入一个值。

计算阶乘还可以采用这个条件表达式的等价形式：

```bash
# F(x):
#   1 >= x ? Q(x) : x * F(x-1)
# Q(x):
#   q()
# F()
[q]sQ [d1!<Q d 1- lFx *]dsFx
```

这个递归过程可以进一步采用尾调用写为：

```bash
# F(x):
#   x
#   1 < x ? G(x) : x
# G(x):
#   F(x-1)
# H(x, acc):
#   x := x * acc
#   1 < z() ? H() : x
# H(F())
[1- lFx]sG [d d1<G]dsFx [* z1<H]dsHx
```

这里的伪代码中的`H(x, acc):`是过程定义，过程`H`消费在栈顶的命名为`acc`的一个值，和紧邻其下的命名为`x`的另一个值；这里的`H()`是过程调用，在调用过程`H`之前不需要向栈顶压入一个值。

这里的运算由两个步骤串接而成，首先将递减的整数压入堆栈形成整数集$\mathbb{Z}$上偏序关系$\ge$的区间$[n, 1]$，然后在这个数列上进行初始值为$1$的应用乘法运算的右侧归约，最终得出一个结果值。这里的命令`z`，将当前的堆栈深度即堆栈中元素数目压入栈顶。还可以进一步增加针对初始的栈顶元素`x`的`x ≤ 0`情况的预处理，即执行`[d-1+]sAd0!<A`来实现`0 >= x ? x-x+1 : x`。下面是其执行示例：

```console
$ echo 0 | dc -e '? [d-1+]sAd0!<A [1- lFx]sG [d d1<G]dsFx [* z1<H]dsHx p'
1
$ echo 9 | dc -e '? [d-1+]sAd0!<A [1- lFx]sG [d d1<G]dsFx [* z1<H]dsHx p'
362880
```

下面的例子采用迭代法打印出阶乘$n! = \prod_{i = 1}^n i$的前`n`项的数列：

```bash
# n := x
# i := 1
# F(x):
#   x := x * i 
#   p(x)
#   i := i + 1
#   n >= i ? F() : x
# F(1)
sn 1si 1 [lid1+si *p liln!<F]dsFx
```

这里`n := x`中的`x`指称初始的栈顶元素。这里的迭代过程`F(x)`不同于一般的递归过程之处，是在调用自身之时仍采用当前栈顶元素为参数而不向堆栈压入新元素。这里所迭代的是需要初始化的堆栈中的自动变量`x`，它是$n!$，其初始值`1`是$0!$；`i`既是迭代的递增计数器，也是迭代二元运算的运算元，其递增形成整数集$\mathbb{Z}$上偏序关系$\le$的区间$[1, n]$，同步地在这个数列上进行输出中间值的初始值为$1$的应用乘法运算的左侧归约，逐项输出中间结果形成数列，这里的`x`所起到的作用也被称为累加器（accumulator），其含义为“累计”或“累积”而不必然采用加法或乘法。

下面是其执行示例：

```console
$ echo 6 | dc -e '? sn 1si 1 [lid1+si *p liln!<F]dsFx'
1
2
6
24
120
720
```

可以将它改为计算单个的阶乘：

```console
$ echo 0 | dc -e '? sn 1si 1 [lid1+si * liln!<F]dsFx p'
1
$ echo 9 | dc -e '? sn 1si 1 [lid1+si * liln!<F]dsFx p'
362880
```

### 斐波那契数

下面是对栈顶元素计算斐波那契数$F_n = F_{n-1} + F_{n-2}$的递归过程，这个过程在`x ≥ 0`时有效，它可直接转写为互递归形式：

```bash
# F(x):
#   1 < x ? G(x) : x
# G(x):
#   F(x-1) + F(x-2)
# F()
[d 2- lFx r 1- lFx +]sG [d1<G]dsFx
```

这里的`r`命令反转（交换）栈顶元素和仅次于栈顶的元素二者的次序，此外dc还有循环移位运算`R`命令，其参数为正数时是循环左移一位，参数为负数时是循环右移一位，参数的绝对值是参与循环移位的堆栈中含栈顶的元素数目，比如后文中用到`_3R`命令会将堆栈顶部的三个元素`a b c`转变为`c a b`。

下面是其执行示例，并展示了通过给它增加统计代码来观察其递归调用的时间复杂度：

```console
$ echo 0 | dc -e '? [d 2- lFx r 1- lFx +]sG [d1<G]dsFx p'
0
$ echo 20 | dc -e '? 0sX [d 2- lFx r 1- lFx +]sG [lX1+sX d1<G]dsFx p [T(n)=]PlXp'
6765
T(n)=21891
$ echo 20 | dc -e '? [[None]pq]sAd3!<A 1+ 7k5v1+2/r^2*5v/ 0k1/ p'
21891
```

这个过程可以进一步采用记忆化，即基于数组的保存命令`:`和访问命令`;`而写为：

```bash
# a[0] := 0
# a[1] := 1
# i := 1
# F(x):
#   i >= x ? N(x) :
#     S(x, b)    
#     temp := G(x)
#     x := L(b)
#     i := x
#     a[x] := temp 
#     temp
# N(x):
#   a[x]
#   q()
# G(x):
#   F(x-1) + F(x-2)
# F()
0 0:a 1 1:a 1si [d 2- lFx r 1- lFx +]sG [;a q]sN [dli!<N dSb lGxd Lbdsi:a]dsFx
```

这里的`i`是数组`a`的已存储过的最大下标，它的初始值是`1`，`a[0]`和`a[1]`已经预先存储了数值。一个过程如果需要在进行过程调用之后仍持有原来的主栈内容，则需要设立并操纵辅助栈，这里的伪代码中的`S(x, b)`表示先复制主栈的栈顶元素再将它移入辅助栈`b`的栈顶，`L(b)`表示弹出辅助栈`b`的栈顶元素并把它压入主栈的栈顶，它们基于了寄存器关联栈的保存命令`S`和装载命令`L`。

在递归定义$F_n = F_{n-1} + F_{n-2}$的递归调用中，随着$F_n$的索引`n`的递减，而递归下降至被计算出来并保存的第一项$F_2 = F_1 + F_0$，然后沿着调用链逐级返回。在递归的每个步骤中都要计算并保存$F_{n}$，它所需要的$F_{n-1}$和$F_{n-2}$这两项之中：

- 如果首先进行$F_{n-2}$递归调用并从其返回，则$F_{n-1}$也需要计算并保存，为此需要先后访问已保存的$F_{n-3}$和$F_{n-2}$。
- 如果首先进行$F_{n-1}$递归调用并从其返回，则需要访问已保存的$F_{n-2}$。

下面是其执行示例，展示了通过给$F_n$加三个打印断点的代码来观察递归调用的具体步骤，其中连续高亮标示出某个过程从开始被调用直到它在数组中保存自己的数值后结束返回：

```console
$ echo 6 | dc -e '?0 0:a1 1:a1si[d2-lFxr1-lFx+]sG[[   Load F(]Pdn[)]P10aP;aq]sN[[Level ]Pzn[ F(]Pdn[)]P10aPdli!<NdSblGxdLbdsi[   Save F(]Pdn[)]P10aP:a]dsFxp'
Level 1 F(6)
Level 2 F(4)
Level 3 F(2)
Level 4 F(0)
   Load F(0)
Level 4 F(1)
   Load F(1)
   Save F(2)
Level 3 F(3)
Level 4 F(1)
   Load F(1)
Level 4 F(2)
   Load F(2)
   Save F(3)
   Save F(4)
Level 2 F(5)
Level 3 F(3)
   Load F(3)
Level 3 F(4)
   Load F(4)
   Save F(5)
   Save F(6)
8
$ echo 6 | dc -e '?0 0:a1 1:a1si[d1-lFxr2-lFx+]sG[[   Load F(]Pdn[)]P10aP;aq]sN[[Level ]Pzn[ F(]Pdn[)]P10aPdli!<NdSblGxdLbdsi[   Save F(]Pdn[)]P10aP:a]dsFxp'
Level 1 F(6)
Level 2 F(5)
Level 3 F(4)
Level 4 F(3)
Level 5 F(2)
Level 6 F(1)
   Load F(1)
Level 6 F(0)
   Load F(0)
   Save F(2)
Level 5 F(1)
   Load F(1)
   Save F(3)
Level 4 F(2)
   Load F(2)
   Save F(4)
Level 3 F(3)
   Load F(3)
   Save F(5)
Level 2 F(4)
   Load F(4)
   Save F(6)
8
```

前面的分析和演示，证实了对数组`a`的存储是按照下标从小至大连续进行的，对这个数组的访问不会出现访问到未曾存储运算结果的空位的异常情况。在递归定义$F_n = F_{n-1} + F_{n-2}$的递归调用中，可以直接将$F_n$的结果存储在`a[++i]`之中，这里有着`i + 1 = n`，故而无需设立并操作辅助栈`b`。递归过程的返回值之间形成了递推关系，每个$F_n$的值被用到一次或两次，首次是从递归调用直接返回，再次是对其已保存的值进行访问，每个步骤要么访问两项并保存两项，要么访问一项并保存一项。这个过程可以进一步写为：

```bash
# i := 1
# F(x):
#   1 < x ? M(x) : x
# M(x):
#   i >= x ? N(x) :
#     temp := G(x)
#     i := i + 1
#     a[i%2] := temp 
#     temp
# N(x):
#   a[x%2]
#   q()
# G(x):
#   F(x-1) + F(x-2)
# F()
1si [d 2- lFx r 1- lFx +]sG [2%;a q]sN [dli!<N lGx dli1+dsi2%:a]sM [d1<M]dsFx
```

在递归定义$F_n = F_{n-1} + F_{n-2}$的上述两种求值次序中，首先进行$F_{n-1}$递归调用的这种形式，其记忆化实现从一开始就持续进行递归调用直到首次递归返回，然后就逐级递归返回而不再进行递归调用，故而它可以进一步写为：

```bash
# a := 0
# F(x):
#   1 < x ? G(x) : x
# G(x):
#   temp := F(x-1)
#   prev := a 
#   a := temp
#   temp + prev
# F()
0sa [1- lFx la r dsa +]sG [d1<G]dsFx
```

这里的`a`被初始化为$F_0$的值`0`，`x`在步入递归调用之后，除了在被递减至$F_1$的值`1`之时作为调用结果来返回之外，没有参与到后续的加法运算之中，而主要起到了递减计数器的作用。

下面的例子采用迭代法打印出斐波那契数列的不含第`0`项的前`n`项：

```bash
# i := x
# a := 1
# F(x):
#   prev := a
#   a := x
#   x := x + prev
#   p(x)
#   i := i - 1
#   0 < i ? F() : x
# 0 < i ? F(0) : 0
si 1sa [lardsa +p li1-si li0<F]sF 0 li0<F
```

这里`i := x`中的`x`指称初始的栈顶元素。这里的迭代过程`F(x)`不同于一般的递归过程之处，是在调用自身之时仍采用当前栈顶元素为参数而不向堆栈压入新元素。针对递推关系$F_{n} = F_{n-1} + F_{n-2}$，它总共进行`n`次迭代运算得出$F_1$到$F_n$。这里的`i`是进行迭代的递减计数器，所迭代的是需要初始化的两个变量`x`和`a`：在堆栈中的自动变量`x`，先是被迭代的$F_{n-1}$，再是迭代出来的$F_{n}$，其初始值`0`是$F_{0}$，它所起到的作用也被称为累加器；作为全局变量的`a`，以$F_1-F_0$所得的`1`作为初始值，在首次迭代之后它是始于$F_0$的$F_{n-2}$。

下面是其执行示例：

```console
$ echo 6 | dc -e '? si 1sa [lardsa +p li1-si li0<F]sF 0 li0<F'
1
1
2
3
5
8
```

可以将它改为计算单个的斐波那契数：

```console
$ echo 0 | dc -e '? si 1sa [lardsa + li1-si li0<F]sF 0 li0<F p'
0
$ echo 21 | dc -e '? si 1sa [lardsa + li1-si li0<F]sF 0 li0<F p'
10946
```

### 男人抑或男孩测试

下面的例子通过男人抑或男孩测试，展示在dc中仅采用数组就能支持递归运算的程度，这个测试用Python可以写为：

```Python
import sys
sys.setrecursionlimit(2**10 + 9) # 这里设置的递归限制在实测时够用于k=10

def A(k, x1, x2, x3, x4, x5):
    def B():
        nonlocal k
        k -= 1
        return A(k, B, x1, x2, x3, x4)
    return x4() + x5() if k <= 0 else B()

print(A(10, lambda:1, lambda:-1, lambda:-1, lambda:1, lambda:0))
```

实现这个测试需要解决的问题，是针对这里的，以同一种方式调用两种闭包：匿名函数即这里的、和，和头等函数即这里的嵌入到包围函数内的嵌套函数，此二者的这些实例皆无参数而可称为thunk。原本的ALGOL 60测试代码，对`x4 + x5`进行有需要时的隐式强制解过程化，现代编程语言一般不提供这种隐式强制特征。

下面是这个测试的dc实现，这里指定了数组`M`为调用栈，其帧指针是`S`而栈指针是`T`：

```bash
# M[0] := S := T := I := 0
# P(): 
#   S := T + 1
#   n := z()
#   T := S + n
#   M := R(n, n)
# R(x, n):
#   M[S+n] := x
#   n := n - 1
#   0 <= n ? R(n) : n
# Q():
#   T := S - 1
#   S := T - M[T]
# U(x):
#   I := I + 1
#   W[I] := x
#   K[I] := S
# V():
#   I := I - 1
# W(i):
#   W[i](i)
0 0:M 0sS 0sT 0sI
[lT1+sS z dlS+sT dlRxsM]sP 
[d_3RlS+:M 1- d0!>R]sR
[lS1-sT lTd;M-sS]sQ
[lI1+sI lI:W lSlI:K]sU
[lI1-sI]sV [d;Wx]sW

# A(k, x1, x2, x3, x4, x5):
#   P(0); F(); Q()
# F():
#   0 >= M[S] ? G() :
#     U('B()'); B(I); V()
# G():
#   M[S+6] := W(M[S+5])
#   W(M[S+4]) + M[S+6]
#   q()
[0lPx lFx lQx]sA
[lS;M0!<G [lBx]lUx lIlBx lVx]sF
[lS5+;M lWx lS6+:M lS4+;M lWx lS6+;M + q]sG

# B(i):
#   L := K[i]
#   J := i
#   M[L] := M[L] - 1
#   A(M[L], J, M[L+1], M[L+2], M[L+3], M[L+4])
[d;KsL sJ lL;M1-lL:M lL;M lJ lL1+;M lL2+;M lL3+;M lL4+;M lAx]sB

# U('(x):1'); U('(x):-1'); U('(x):-1'); U('(x):1'); U('(x):0')
# p(A(?(), 1, 2, 3, 4, 5))
[sM1]lUx [sM_1]lUx [sM_1]lUx [sM1]lUx [sM0]lUx
? 1 2 3 4 5 lAx p
```

这里的帧指针`S`指向调用栈顶部栈帧的底部，这个栈帧的内容是当前执行函数的实际参数列表，加上这个函数中存储其运算所用到的中介值或临时值的局部变量的初始值；最后是前述实际项目的数量`n`，它可视为描述此栈帧的元数据。栈指针`T`指向整个堆栈的顶部，在项目压入新建栈帧之后，它也是这个顶部栈帧的顶部，即`T := S + n`，其内容就是数量`n`，即`M[T] := n`。

将项目压入栈帧采用了辅助过程`R(n, n)`，它将在主栈中所有的实际参数和局部变量初始值以及项目数量`n`，压入调用栈`M`的当前栈帧相对于帧指针`S`偏移量`0`至`n`的位置，它能够妥善处理传递给`printf(<small>格式</small>, ...)`样式的可变参数函数的可变参数列表。

在这里的调用约定中实际参数由被调用者清理。在进行堆栈回溯之时，被调用者帧指针`S`减`1`就是调用者栈帧的栈指针`T'`，即`T' = S - 1`。栈指针`T`减去其内容`M[T]`就得到帧指针，即`S := T - M[T]`，这里不需要为复原帧指针而在栈帧中专门存储控制链接。没有实际内容的空栈帧占用调用栈`M`的一个位置，有着`M[T] := 0; S := T`。

这里采用了传统Unix哲学的平行数组策略，将无参数匿名函数实现为常量函数，从而将两种闭包统一存储在以`I`为最大索引值的数组`W`之中，并以在这个闭包数组中的位置索引作为其标识符，以这种标识符为参数的函数调用可称为传名调用。另立数组`K`储存以实际参数形式提供给嵌套函数`B(i)`进行非局部变量的静态链接，也就是包围函数`A()`的帧指针`S'`。

执行闭包采用了辅助过程`W(i)`，它以闭包标识符为索引从数组`W`中取出闭包，再以这个标识符为参数调用这个闭包；常量函数比如`[sM1]`会直接忽略参数值返回常量值，而闭包`[lBx]`执行嵌套函数`B(i)`，它以这个标识符为索引从数组`K`中取出静态链接存入变量`L`中用来进行非局部引用，这里的`i`的作用相当于支持面向对象编程范型的Modula-3和Python中方法的第一个形式参数`this (计算机编程)`。

将上述代码保存入`manorboy.dc`文件中，下面是针对`k`为`0`到`10`它的执行示例：

```console
$ for i in $(seq 0 10); do echo $i | dc manorboy.dc; done
1
0
-2
0
1
0
1
-1
-10
-30
-67
```

对于`k = 10`，这个测试中包围函数`A()`，被嵌套函数`B(i)`所直接调用，再加上它的顶层调用，总共执行了`722`次；嵌套函数`B(i)`，要么被包围函数`A()`所直接调用，要么作为包围函数`A()`的传名形式参数被求值，总共执行了`721`次。在嵌套函数`B(i)`每次被直接调用之前，为它创建一个闭包，总共为它创建了`416`个闭包，它们作为传名形式参数，总共被求值了`721 - 416 = 305`次。在包围函数`A()`的顶层调用之前，为常量函数创建了`5`个闭包，它们总共被执行了`66 + 85 + 102 + 54 + 0 = 307`次，从而得出了最终的运算结果`66 - 85 - 102 + 54 = -67`。

这里的包围函数`A()`在传值形式参数`k`小于等于零的情况下，先求值第`5`个传名形式参数再求值第`4`个传名形式参数，包围函数`A()`在调用栈中的栈帧数量的最大值即递归深度是`323`层，嵌套函数`B(i)`在其存储数组中堆叠数量的最大值是`258`层。如果在包围函数`A()`中先求值第`4`个传名形式参数再求值第`5`个传名形式参数，包围函数`A()`的递归深度为`512`层，嵌套函数`B(i)`堆叠数量的最大值是`384`层。

下面的dc实现改变策略，将闭包作为最后项目压入栈帧之中：

```bash
# M[0] := S := T := 0
# P(): 
#   S := T + 1
#   n := z()
#   T := S + n
#   M := R(n, n)
# R(x, n):
#   M[S+n] := x
#   n := n - 1
#   0 <= n ? R(n) : n
# Q():
#   T := S - 1
#   S := T - M[T]
# W(i):
#   M[i](i)
0 0:M 0sS 0sT
[lT1+sS z dlS+sT dlRxsM]sP 
[d_3RlS+:M 1- d0!>R]sR
[lS1-sT lTd;M-sS]sQ
[d;Mx]sW

# A(k, x1, x2, x3, x4, x5):
#   P(0, 'B()'); F(); Q()
# F():
#   0 >= M[S] ? G() : B(T-1)
# G():
#   M[S+6] := W(M[S+5])
#   W(M[S+4]) + M[S+6]
#   q()
[0[lBx]lPx lFx lQx]sA
[lS;M0!<G lT1-lBx]sF
[lS5+;M lWx lS6+:M lS4+;M lWx lS6+;M + q]sG

# B(i):
#   L := i+1 - M[i+1]
#   J := i
#   M[L] := M[L] - 1
#   A(M[L], J, M[L+1], M[L+2], M[L+3], M[L+4])
[d1+d;M-sL sJ lL;M1-lL:M lL;M lJ lL1+;M lL2+;M lL3+;M lL4+;M lAx]sB

# P('(x):1', '(x):-1', '(x):-1', '(x):1', '(x):0')
# p(A(?(), 1, 2, 3, 4, 5))
[sM1] [sM_1] [sM_1] [sM1] [sM0] lPx
? 1 2 3 4 5 lAx p
```

在栈帧中存储执行嵌套函数`B(i)`的闭包项目`[lBx]`的作用，是让它通过自己在栈帧中的相对位置，找到包围函数`A()`的栈指针`T'`，从而计算出进行非局部引用所需的包围函数`A()`的帧指针`S'`并存入变量`L`之中。如果要将这里的调用栈机制普遍化，比如在栈帧存入更多其他的嵌套函数，可以将它在栈帧中项目相对于栈指针的偏移量也存储在其旁边。

与这个测试的Python实现相比，这里的嵌套函数`B(i)`由于没有调用者在主栈中传递给它的实际参数和自己的局部变量，并且结束于尾调用，故而没有创建自己的栈帧。嵌套函数`B(i)`如果要创建自己的栈帧，可以将闭包调用辅助过程`W(i)`在主栈中传递给它的其在调用栈的位置参数`i`转存入自己的栈帧：

```bash
# B(i):
#   P()
#   L := M[S]+1 - M[M[S]+1]
#   M[L] := M[L] - 1
#   A(M[L], M[S], M[L+1], M[L+2], M[L+3], M[L+4])
#   Q()
[lPx lS;M1+d;M-sL lL;M1-lL:M lL;M lS;M lL1+;M lL2+;M lL3+;M lL4+;M lAx lQx]sB
```

嵌套函数`B(i)`如果创建了自己的栈帧，那么它在调用栈中的递归深度，比包围函数`A()`的递归深度少`1`层。

## 外部链接

- 软件包 dc在Debian GNU/Linux仓库中
- bc的 原生Windows移植包括了dc
- 嵌入到网页中的dc
- The unix dc(1) command, this is the esoteric language that "made it big".

## 基本资料

- 日语原文：dc
- 作者：Robert Morris、（于AT&T贝尔实验室）、Lorinda Cherry
- 开发者：各种开源和商业开发者
- 编程语言：B, C
- 操作系统：Unix, 类Unix, Plan 9
- 平台：跨平台
- 类型：命令
- 编程范型：多范型: 面向堆栈, 串接式
- 类型系统：无类型（所有数据都是任意精度数值）
- 受影响于：RPN