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