dc (程序)

dc

原作者	Robert Morris （于AT&T贝尔实验室） Lorinda Cherry
开发者	各种开源和商业开发者
编程语言	B
操作系统	Unix, 类Unix, Plan 9
平台	跨平台
类型	命令

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

历史

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

基本运算

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

$ dc
4 5 *
p
20
q

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

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

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

$ dc -e '10946 6765 / p'
1

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

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

dc有科学计算器的基本运算功能，比如求黄金分割率${\textstyle {\frac {{\sqrt {5}}+1}{2}}}$的值：

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

dc将输入数值的前导_识别为负号，命令^计算幂，命令v计算平方根。

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

输入/输出

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

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

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

$ echo '16o2i 1001101010111100110111101111 p' | dc
9ABCDEF

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

语言特征

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

寄存器

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

3 sc 4 lc * p

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

字符串

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

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

宏

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

[1 + 2 *]sm

通过使用x命令弹出栈顶的字符串并执行之，如下这样使用存储的宏：

3 lmx p

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

条件

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

[[equal]p]sm d5=m

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

$ echo 5 | dc -e '? [[equal]p]sm d5=m'
equal
$ echo 5 | dc -e '? [[[equal]pq]sm d5=m [not equal]p]x'
equal
$ echo 4 | dc -e '? [[[equal]pq]sm d5=m [not equal]p]x'
not equal

迭代示例

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

阶乘

下面是采用了互递归对栈顶元素计算阶乘${\textstyle n!=n\cdot (n-1)!}$的过程：

# F(x):
#   x > 1 ? G(x) : x
# G(x):
#   x * F(x-1)

它在x > 0时有效，这里的伪代码采用了条件运算符而非条件语句。它可实现为：

[d 1- lFx *]sG [d1<G]dsFx

它可以进一步采用尾递归实现为：

[d 1- lFx]sG [d1<G]dsFx 1 [* z1<H]dsHx

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

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

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

# n := x
# i := 0
# F(x):
#   i := i + 1
#   x := x * i 
#   print(x)
#   i < n ? F(x) : x
# F(1)

这里迭代的是需要初始化的堆栈中的自动变量x，它是$n!$，其初始值1是$0!$；i既是迭代的递增计数器，也是迭代二元运算的运算元，其递增形成整数集$\mathbb {Z}$上偏序关系$\leq$的区间$[1,n]$，同步地在这个数列上进行输出中间值的应用乘法运算的左归约得出结果数列，这里的x所起到的作用也被称为累加器，其含义为“累计”或“累积”而不必然采用加法或乘法。它可实现为：

sn 0si 1 [li1+dsi *p liln>F]dsFx

下面是其执行示例：

$ echo 6 | dc -e '? sn 0si 1 [li1+dsi *p liln>F]dsFx'
1
2
6
24
120
720

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

$ echo 0 | dc -e '? sn 0si 1 [li1+dsi * liln>F]dsFx p'
1
$ echo 9 | dc -e '? sn 0si 1 [li1+dsi * liln>F]dsFx p'
362880

斐波那契数

下面是采用了互递归的对栈顶元素计算斐波那契数的过程：

# F(x):
#   x > 1 ? G(x) : x
# G(x):
#   F(x-1) + F(x-2)

可实现为：

[d 2- lFx r 1- lFx +]sG [d1<G]dsFx

这里的r命令反转（交换）栈顶元素和仅次于栈顶的元素二者的次序。它可以进一步采用记忆化而写为：

# F(x):
#   x > 1 ? M(x) : x
# M(x):
#   if x in a
#     a[x]
#   else 
#     temp := G(x)
#     a[x] := temp 
#     temp
# G(x):
#   F(x-1) + F(x-2)

基于数组保存命令:和访问命令;，它可实现为：

0Sa 1si [d 2- lFx r 1- lFx +]sG [;aq]sN [dli!<N lGx dli1+dsi:a]sM [d1<M]dsFx Lasa

或者更一般化的写为：

# a[0] := 0
# a[1] := 1
# F(x):
#   if x in a
#     a[x]
#   else 
#     temp := G(x)
#     a[x] := temp 
#     temp
# G(x):
#   F(x-1) + F(x-2)

它可实现为：

0Sa 0 0:a 1 1:a 1si [d 2- lFx r 1- lFx +]sG [;aq]sN [dli!<N lGx dli1+dsi:a]dsFx Lasa

下面是其执行示例，展示了通过给它加打印断点来观察其递归调用的规模和详细步骤：

$ echo 0 | dc -e '? [d 2- lFx r 1- lFx +]sG [d1<G]dsFx p'
0
$ echo 20 | dc -e '? [d 2- lFx r 1- lFx +]sG [d1<G]dsFx p'
6765
$ echo 21 | dc -e '? [d 2- lFx r 1- lFx +]sG [d1<G]dsFx p'
10946
$ echo 20 | dc -e '? [p d 2- lFx r 1- lFx +]sG [d1<G]dsFx' | wc -l
10945
$ echo 20 | dc -e '? 0Sa 0 0:a 1 1:a 1si [d 2- lFx r 1- lFx +]sG [;aq]sN [p dli!<N lGx dli1+dsi:a]dsFx Lasa' | wc -l
39
$ echo 6 | dc -e '? 0Sa 1si [d 2- lFx r 1- lFx +]sG [;aq]sN [zn[ F]np dli!<N lGx dli1+dsi:a]sM [d1<M]dsFx Lasa'
1 F6
2 F4
3 F2
3 F3
4 F2
2 F5
3 F3
3 F4
$ echo 6 | dc -e '? 0Sa 1si [d 1- lFx r 2- lFx +]sG [;aq]sN [zn[ F]np dli!<N lGx dli1+dsi:a]sM [d1<M]dsFx Lasa'
1 F6
2 F5
3 F4
4 F3
5 F2
4 F2
3 F3
2 F4

在递归定义$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-2}$和$F_{n-3}$；如果首先进行$F_{n-1}$递归调用并从其返回，则需要访问已保存的$F_{n-2}$；这种递归返回形成了递推关系，每个$F_{n}$的值被用到一次或两次，首次是从递归调用直接返回，再次是对其已保存的值进行访问，每个步骤要么访问两项并保存两项，要么访问一项并保存一项。故而它可以进一步写为：

1si [d 2- lFx r 1- lFx +]sG [2%;aq]sN [dli!<N lGx dli1+dsi2%:a]sM [d1<M]dsFx

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

# a := 0
# F(x):
#   x > 1 ? G(x) : x
# G(x):
#   curt := F(x-1)
#   prev := a 
#   a := curt
#   curt + prev

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

0sa [1- lFx la r dsa +]sG [d1<G]dsFx

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

# i := x
# a := 1
# F(x):
#   i > 0 ? G(x) : x
# G(x):
#   prev := a
#   a := x
#   x := x + prev
#   print(x)
#   i := i - 1
#   F(x)
# F(0)

针对递推关系$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}$。它可实现为：

si 1sa 0 [lardsa +p li1-si lFx]sG [li0<G]dsFx

下面是其执行示例：

$ echo 6 | dc -e '? si 1sa 0 [lardsa +p li1-si lFx]sG [li0<G]dsFx'
1
1
2
3
5
8

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

$ echo 0 | dc -e '? si 1sa 0 [lardsa + li1-si lFx]sG [li0<G]dsFx p'
0
$ echo 9 | dc -e '? si 1sa 0 [lardsa + li1-si lFx]sG [li0<G]dsFx p'
34

参见

• bc
• 逆波兰表示法
• 面向堆栈编程
• 隐式编程
• 堆栈机器

外部链接

• 软件包dc（页面存档备份，存于互联网档案馆）在Debian GNU/Linux仓库中
• bc的原生Windows移植包括了dc
• 嵌入到网页中的dc（页面存档备份，存于互联网档案馆）
• The unix dc(1) command, this is the esoteric language that "made it big". （页面存档备份，存于互联网档案馆）