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):
#   if x > 1
#     x * F(x-1)
#   else 
#     x

它在x > 0時有效，它可採用互遞迴寫為：

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

這裡的虛擬碼採用了條件運算子而非條件語句。它可實現為：

[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):
#   if x > 1 
#     F(x-1) + F(x-2)
#   else
#     x

它在x ≥ 0時有效，它可採用互遞迴寫為：

# 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". （頁面存檔備份，存於網際網路檔案館）