dc (程序)
| 原作者 | Robert Morris （于AT&T贝尔实验室） Lorinda Cherry |
|---|---|
| 开发者 | 各种开源和商业开发者 |
| 编程语言 | B, C |
| 操作系统 | Unix, 类Unix, Plan 9 |
| 平台 | 跨平台 |
| 类型 | 命令 |
dc（desk calculator：桌面计算器）是采用逆波兰表示法的跨平台计算器，它支持任意精度算术[1]。它是Robert Morris在贝尔实验室工作期间书写的[2]，作为最老的Unix实用工具，先于C语言的发明。像那个年代的其他实用工具一样，它有着一组强力的特征和简洁的语法[3][4]。传统上，采用中缀表示法的bc计算器程序是在dc之上实现的。
历史
[编辑]dc是幸存的最老的Unix语言[2]。在贝尔实验室收到第一台PDP-11的时候，用B语言写成的dc是在这个新机器上运行的第一个语言，甚至在汇编器之前[5]。
基本运算
[编辑]在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有科学计算器的基本运算功能，比如求黄金分割率的值：
$ 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 10011010101111001101111011110000 p' | dc
9ABCDEF0
要读取设置的这些数值，K、I和O命令将压入当前精度、输入基数和输出基数到栈顶。
语言特征
[编辑]除了上述的基本算术和栈操作，dc包括了对宏、条件和存储结果用于以后检索的支持。
寄存器
[编辑]寄存器在dc中是有着单一字符名字的存贮位置，它可以分别通过命令s和l来存储和检索，它是宏和条件的底层机制：sc弹出栈顶元素并将它存储入寄存器c，而lc将寄存器c的值压入栈顶。例如：
3 sc 4 lc * p寄存器还被当作次要栈，可以使用S和L命令在它们和主要栈之间压入和弹出数值。存储栈顶元素到寄存器中并把这个元素留在栈顶，需要联合使用ds命令。
字符串
[编辑]字符串是包围在[和]之中的字符，可以被压入栈顶和存入寄存器。使用x命令从栈顶弹出字符串并执行它，使用P命令从栈顶弹出并打印字符串，无尾随换行。a命令可以把数值的低位字节转换成ASCII字符，或者在栈顶是字符串时把它替换为这个字符串的第一个字符。此外没有方法去建造字符串或进行字符串操纵。
#字符开始一个注释直到此行结束。
宏
[编辑]通过允许寄存器和栈项目像数值一样存储字符串，从而实现了宏。一个字符串可以被打印，也可以被执行，就是说作为dc命令的序列而传递。例如可以把一个宏“加1并接着乘以2”存储到一个寄存器M中：
[1+ 2*]sM下面的命令将一个数值3压入栈顶，使用x命令执行存储在寄存器M中的宏，并打印留在栈顶的结果：
3 lMx p条件
[编辑]最后提供了有条件执行宏的机制。命令=M将从栈顶弹出两个值，如果二者相等，则执行存储在寄存器M中的宏。如下命令序列将在原栈顶元素等于5的条件下打印字符串equal。
[[equal]p]sM d5=M这里使用了d命令保留原栈顶元素。其他条件有>、!>、<、!<、!=，如果栈顶元素分别大于、不大于（小于等于）、小于、不小于（大于等于）、不等于仅次于栈顶的元素，则执行指定的宏。注意不同于Forth、PostScript和Factor，在不等式比较中的运算元的次序同在算术中的次序相反，5 3 - 等价于中缀表示法的5-3，然而5 3< R在3<5时运行寄存器R的内容。下面是有条件执行宏的示例：
$ echo 5 | dc -e '? [[equal]p]sM d5=M'
equal
$ echo 4 | dc -e '? [[equal]p]sM d5=M'
$
这里的命令在栈顶元素等于5之时有相应的输出，在它不等于5之时没有输出。
如果要实现一般编程语言中表达分支控制流程的条件运算符?:或条件语句，则需要2个宏构造，例如：
$ 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。
递归示例
[编辑]通过定义进行有条件的递归调用的宏，可以实现递归过程和迭代运算。
阶乘
[编辑]
# F(x):
# x > 1 ? x * F(x-1) : x
# F()本文中的伪代码尽量采用条件运算符?:，只在确有两个分支之时采用条件语句。这里的F(x):是过程定义，过程F消费在栈顶的命名为x的一个值；这里的F(x-1)是过程调用，在调用过程F之前先将x-1的结果值压入栈顶；这里的F()也是过程调用，在调用过程F之前不需要向栈顶压入一个值。
这个过程在x > 0时有效，它可直接转写为互递归形式：
# F(x):
# x > 1 ? G(x) : x
# G(x):
# x * F(x-1)
# F()它可实现为：
[d 1- lFx *]sG [d1<G]dsFx计算阶乘还可以采用这个条件表达式的等价形式：
# F(x):
# x <= 1 ? x : x * F(x-1)
# F()它可实现为：
[q]sQ [d1!<Q d 1- lFx *]dsFx这个递归过程可以进一步采用尾调用写为：
# F(x):
# x
# x > 1 ? G(x) : x
# G(x):
# F(x-1)
# H(x, acc):
# x := x * acc
# z() > 1 ? H() : x
# H(F())这里的伪代码中的H(x, acc):是过程定义，过程H消费在栈顶的命名为acc的一个值，和紧邻其下的命名为x的另一个值；这里的H()是过程调用，在调用过程H之前不需要向栈顶压入一个值。它可实现为：
[1- lFx]sG [d d1<G]dsFx [* z1<H]dsHx这里的运算由两个步骤串接而成，首先将递减的整数压入堆栈形成整数集上偏序关系的区间，然后在这个数列上进行初始值为的应用乘法运算的右侧归约，最终得出一个结果值。这里的命令z，将当前的堆栈深度即堆栈中元素数目压入栈顶。还可以进一步增加针对初始的栈顶元素x的x ≤ 0情况的预处理，即执行x := x-x+1来实现x := 1。下面是其执行示例：
![{\displaystyle [n,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27832ea7651e60b4d0f0190a6aa07ce5cbe166a9)
$ 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 := x
# i := 1
# F(x):
# x := x * i
# p(x)
# i := i + 1
# i <= n ? F() : x
# F(1)这里n := x中的x指称初始的栈顶元素。这里的迭代过程F(x)不同于一般的递归过程之处，是在调用自身之时仍采用当前栈顶元素为参数而不向堆栈压入新元素。这里所迭代的是需要初始化的堆栈中的自动变量x，它是，其初始值1是；i既是迭代的递增计数器，也是迭代二元运算的运算元，其递增形成整数集上偏序关系的区间，同步地在这个数列上进行输出中间值的初始值为的应用乘法运算的左侧归约，逐项输出中间结果形成数列，这里的x所起到的作用也被称为累加器（accumulator），其含义为“累计”或“累积”而不必然采用加法或乘法。它可实现为：
![{\displaystyle [1,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c79af450e22e8fd23f28e6be4cb23a47b24c1ba)
sn 1si 1 [lid1+si *p liln!<F]dsFx下面是其执行示例：
$ echo 6 | dc -e '? sn 1si 1 [lid1+si *p liln!<F]dsFx'
1
2
6
24
120
720
可以将它改为计算单个的阶乘：
$ 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(x):
# x > 1 ? F(x-1) + F(x-2) : x
# F()这个过程在x ≥ 0时有效，它可直接转写为互递归形式：
# F(x):
# x > 1 ? G(x) : x
# G(x):
# F(x-1) + F(x-2)
# F()它可实现为：
[d 2- lFx r 1- lFx +]sG [d1<G]dsFx这里的r命令反转（交换）栈顶元素和仅次于栈顶的元素二者的次序。下面是其执行示例，并展示了通过给它加打印断点来观察其递归调用的规模：
$ 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 20 | dc -e '? [p d 2- lFx r 1- lFx +]sG [d1<G]dsFx' | wc -l
10945
$ echo 21 | dc -e '? [d 2- lFx r 1- lFx +]sG [d1<G]dsFx p'
10946
这个过程可以进一步采用记忆化而写为：
# i := 1
# F(x):
# x > 1 ? M(x) : x
# M(x):
# if x <= i
# a[x]
# else
# temp := G(x)
# i := i + 1
# a[i] := temp
# temp
# G(x):
# F(x-1) + F(x-2)
# F()基于数组的保存命令:和访问命令;，它可实现为：
1si [d 2- lFx r 1- lFx +]sG [;a q]sN [dli!<N lGx dli1+dsi:a]sM [d1<M]dsFx在递归定义中，正在计算并要记忆其结果的是，即将它的结果存储在这里的a[n]中，其下标为n，而当前已存储过的最大下标是n-1，将要存储的下标是已经存储的最大下标的增加1。这里的i是数组a的已存储过的最大下标，它的初始值是1，即假定a[0]和a[1]已经存储了数值。这里的F(x)在被遇到0和1这两个参数之时，直接在代码中返回数值，而不会用它们作为下标去访问数组。
这个过程可以更一般化的写为：
# a[0] := 0
# a[1] := 1
# i := 1
# F(x):
# if x <= i
# a[x]
# else
# S(x, b)
# temp := G(x)
# x := L(b)
# i := x
# a[x] := temp
# temp
# G(x):
# F(x-1) + F(x-2)
# F()这里的伪代码中的S(x, b)表示复制主栈的栈顶元素x并把它压入栈b的栈顶，L(b)表示弹出栈b的栈顶元素并把它压入主栈的栈顶。基于寄存器关联栈的保存命令S和装载命令L，它可实现为：
0 0:a 1 1:a 1si [d 2- lFx r 1- lFx +]sG [;a q]sN [dli!<N dSb lGxd Lbdsi:a]dsFx在递归定义的递归调用中，随着的索引n的递减，而递归下降至被计算出来并保存的第一项，然后沿着调用链逐级返回。在递归的每个步骤中都要计算并保存，它所需要的和这两项之中：
- 如果首先进行递归调用并从其返回，则也需要计算并保存，为此需要先后访问已保存的和；
- 如果首先进行递归调用并从其返回，则需要访问已保存的。
下面是其执行示例，展示了通过给它加打印断点来观察其递归调用的具体步骤，其中连续高亮标示出在调用栈中一个过程从开始被调用直到它结束返回：
$ echo 8 | dc -e '? 0 0:a 1 1:a 1si [d 2- lFx r 1- lFx +]sG [;a q]sN [[Level]nzn[ F]np dli!<N dSb lGxd Lbdsi:a]dsFx'
Level1 F8
Level2 F6
Level3 F4
Level4 F2
Level5 F0
Level5 F1
Level4 F3
Level5 F1
Level5 F2
Level3 F5
Level4 F3
Level4 F4
Level2 F7
Level3 F5
Level3 F6
$ echo 8 | dc -e '? 0 0:a 1 1:a 1si [d 1- lFx r 2- lFx +]sG [;a q]sN [[Level]nzn[ F]np dli!<N dSb lGxd Lbdsi:a]dsFx'
Level1 F8
Level2 F7
Level3 F6
Level4 F5
Level5 F4
Level6 F3
Level7 F2
Level8 F1
Level8 F0
Level7 F1
Level6 F2
Level5 F3
Level4 F4
Level3 F5
Level2 F6
递归过程的返回值之间形成了递推关系，每个的值被用到一次或两次，首次是从递归调用直接返回，再次是对其已保存的值进行访问，每个步骤要么访问两项并保存两项，要么访问一项并保存一项。故而它可以进一步写为：
# i := 1
# F(x):
# x > 1 ? M(x) : x
# M(x):
# if x <= i
# a[x%2]
# else
# temp := G(x)
# i := i + 1
# a[i%2] := temp
# temp
# 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在递归定义的上述两种求值次序中，首先进行递归调用的这种形式，其记忆化实现从一开始就持续进行递归调用直到首次递归返回，然后就逐级递归返回而不再进行递归调用，故而它可以进一步写为：
# a := 0
# F(x):
# x > 1 ? G(x) : x
# G(x):
# temp := F(x-1)
# prev := a
# a := temp
# temp + prev
# F()这里的a被初始化为的值0，x在步入递归调用之后，除了在被递减至的值1之时作为调用结果来返回之外，没有参与到后续的加法运算之中，而主要起到了递减计数器的作用。它可实现为：
0sa [1- lFx la r dsa +]sG [d1<G]dsFx下面的例子采用迭代法打印出斐波那契数列的不含第0项的前n项：
# i := x
# a := 1
# F(x):
# prev := a
# a := x
# x := x + prev
# p(x)
# i := i - 1
# i > 0 ? F() : x
# i > 0 ? F(0) : 0这里i := x中的x指称初始的栈顶元素。这里的迭代过程F(x)不同于一般的递归过程之处，是在调用自身之时仍采用当前栈顶元素为参数而不向堆栈压入新元素。针对递推关系，它总共进行n次迭代运算得出到。这里的i是进行迭代的递减计数器，所迭代的是需要初始化的两个变量x和a：在堆栈中的自动变量x，先是被迭代的，再是迭代出来的，其初始值0是，它所起到的作用也被称为累加器；作为全局变量的a，以所得的1作为初始值，在首次迭代之后它是始于的。它可实现为：
si 1sa [lardsa +p li1-si li0<F]sF 0 li0<F下面是其执行示例：
$ echo 6 | dc -e '? si 1sa [lardsa +p li1-si li0<F]sF 0 li0<F'
1
1
2
3
5
8
可以将它改为计算单个的斐波那契数：
$ echo 0 | dc -e '? si 1sa [lardsa + li1-si li0<F]sF 0 li0<F p'
0
$ echo 9 | dc -e '? si 1sa [lardsa + li1-si li0<F]sF 0 li0<F p'
34
参见
[编辑]引用
[编辑]- ^ : an arbitrary precision calculator – Linux用户命令（User Commands）手册页
- ^ 2.0 2.1 Brian Kernighan and Ken Thompson. A nerdy delight for any Vintage Computer Fest 2019 attendee: Kernighan interviewing Thompson about Unix. YouTube. 事件发生在 29m45s. [September 3, 2019]. （原始内容存档于2022-02-01）.
- ^ The sources for the manual page for 7th Edition Unix dc. [2020-09-25]. （原始内容存档于2019-09-24）.
- ^ Ritchie, Dennis M. The Evolution of the Unix Timesharing System. Sep 1979 [2019-05-31]. （原始内容存档于2010-05-06）.
- ^ McIlroy, M. D. A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986 (PDF) (技术报告). CSTR. Bell Labs. 1987 [2019-05-31]. 139. （原始内容存档 (PDF)于2019-11-30）.
