Dc (UNIX)

**dc** (*desk calculator*; 卓上計算機の意) は、任意精度の演算をサポートする、クロスプラットフォームな逆ポーランド記法の計算機ユーティリティである。ロバート・モリスがベル研究所にいる間に開発されたこのソフトウェアは、最も古い Unix ユーティリティのひとつで、これは C 言語の発明よりも前のことである。同世代の他のユーティリティのように一連の強力な機能を持っているが、その構文は簡潔である。伝統的に、中間記法の計算機ユーティリティである bc は dc をバックエンドプロセスとして利用していた。

ここでは、言語の一般的な傾向を示すためにいくつかの例を紹介している。完全なコマンドと構文については、それぞれの実装による man ページを参照されたい。

## 歴史
dc は現存する Unix 言語の中で最も古いものである。ベル研究所に PDP-11 が導入されたときには、アセンブラよりも先に、(B 言語で書かれた) dc がそのマシンで動く最初の言語なった。ケン・トンプソンは、dc がこのマシンで書かれた最初のプログラムだとも発言している。

## 基本的な演算
dc で 4 \times 5 を計算するには次のように実行する (空白文字のほとんどは省略可能):
```console
$ cat << EOF > cal.txt
4 5 *
p
EOF

$ dc cal.txt
20
$
```
次のコマンドを使用して結果を得ることもできる:
```console
$ echo "4 5 * p" | dc
```
あるいは:
```console
$ dc -
4 5*pq
20

$ dc
4 5 *
p
20
q

$ dc -e '4 5 * p'
```
これらの動作は「4 と 5 をスタックにプッシュし、乗算演算子 (`*`) によってスタックから要素を 2 つポップし、それらをかけ合わせた値をスタックにプッシュする」ものである。`p` コマンドはスタックの先頭の要素を表示する。`q` コマンドは dc プログラムを終了する。演算子同士や演算子と数字の間のスペースは省略できるが、数字同士の間のスペースは省略できないことに注意する。また、数値は `3.14` や `.318` などの小数であってもよいが、指数表記 (1.23e4 のような表記) には対応していない。

演算の精度 (演算で有効とする小数点以下の桁数) を変更するには `k` コマンドを利用する。起動時のデフォルト値は 0 であるので、次の dc コマンドの結果は **<code>0</code>** となる:
 2 3 / p
`k` コマンドを利用して適当な精度に設定することで、任意の小数点以下の桁を演算できる。次の dc コマンドの結果は **<code>.66666</code>** となる:
 5 k
 2 3 / p
次の dc コマンドは \sqrt{\frac{12+(-3)^4}{11}}-22 を計算する (`v` コマンドはスタックの先頭の平方根を演算し、`_` は負値の負符号である):
 12 _3 4 ^ + 11 / v 22 - p
その他にも、スタックの先頭 2 つの要素の順を入れ替える `r` コマンドやスタックの先頭の要素を複製する `d` コマンドなどがある。

## 入出力
`?` コマンドを利用して標準入力を 1 行読み込むことができる。このコマンドは入力された行を dc コマンドとして評価する。そのため、入力は dc コマンドとして正しい構文である必要があるほか、`!` コマンドを利用して任意のユーザコマンドを実行できるため、セキュリティ上の問題が発生する恐れすらある。

前述したとおり、`p` コマンドはスタックの先頭の要素を表示して改行する。`n` コマンドはスタックからポップした値を改行を伴わずに表示する。`f` コマンドはスタックの内容を先頭から順にすべて表示する。

dc はまた、入力と出力に利用する基数を任意に設定できる。`i` コマンドは入力時の基数としてスタックをポップした値を設定する。dc コマンドとの衝突を避けるため、利用できる基数は 2 から 16 に限られ、基数に 10 以上を指定する場合は A から F の大文字を数として利用する (小文字は利用できない)。同様に `o` コマンドは出力時の基数としてスタックからポップした値を設定する。また、現在の精度・入力基数・出力基数を得るためには、`K`・`I`・`O` コマンドを利用する。これらは現在の値をスタックにプッシュする。

以下に示すのは 16 進数の入力を 2 進数に変換する例である:
```console
$ echo 16i2o DEADBEEF p | dc
11011110101011011011111011101111
```


## 言語の特徴的な機能
dc は、上で述べた基本的な演算やスタック操作に加えて、マクロ、条件分岐、演算結果の一時保存などの機能を備えている。

### レジスタ
dc におけるレジスタは、マクロや条件式の基本となる仕組みである。それぞれのレジスタは 1 文字の名前を持っている。レジスタを利用して値を保存したりスタックに取り出したりすることができる。`s''c''` コマンドはスタックからポップした要素をレジスタ *c* に保存する。`l''c''` コマンドは *c* レジスタの値をスタックにプッシュする。以下に示すのはレジスタを利用する例である:
 3 sc 4 lc * p
レジスタをスタックとして利用することもできる。メインのスタックとレジスタのスタックとの間でプッシュ・ポップするには `S`・`L` コマンドを利用する。

### 文字列
dc では `[` と `]` で囲まれたものを文字列値として扱う。文字列も数値と同様にスタックにプッシュしたりレジスタに格納したりできる。`a` コマンドはスタックから要素をポップし、それが数値である場合は下位バイトを ASCII 文字に変換してプッシュし、文字列の場合は最初の 1 文字をプッシュする。文字列を `x` コマンドでマクロとして実行したり `P` コマンドで表示することはできるが、文字列を構築したり文字列操作を行う方法はない。

また、dc では `#` から行末までをコメントとして扱い、実行には影響を及ぼさない。

### マクロ
dc ではレジスタやスタックに数値だけでなく、文字列を格納できるようにすることでマクロ機能を実現している。文字列は表示するだけでなく、それ自身を dc コマンドとして実行することもできる。以下に示すのは 1 を加算して 2 を掛けるマクロをレジスタ m に格納する例である:
 [1 + 2 *] sm
そして次のようにマクロを呼び出す (`x` コマンドはスタックからポップした値をマクロとして実行する):
 3 lm x p

### 条件分岐
マクロの仕組みを利用して条件分岐を行うことができる。`=''r''` コマンドはスタックから要素を 2 つポップし、それらの値が等しいときにレジスタ *r* に格納されているマクロを実行する。以下に示すのはスタックの先頭に 5 があるときに **<code>Equal</code>** と表示する例である:
 
その他にも、`>` (もともとの先頭が大きい場合にマクロ実行)、`!>` (大きくない場合)、`<` (小さい場合)、`!<` (小さくない場合)、`!=` (等しくない場合) がある。

### ループ
dc でループそのものを行う方法はないが、マクロを再帰的に実行することで再現できる。スタックの先頭の要素の階乗を求めるには次のようにする:
 # F(x): return x!
 # if x-1 > 1
 #     return x * F(x-1)
 # otherwise
 #     return x
 [d1-d11Q コマンドはマクロから脱出する。これに対して `q` コマンドはそのマクロとそのマクロを呼び出したマクロから脱出する。マクロの呼び出し深度が 2 未満の場合は dc プログラムをも終了する。`z` コマンドは現在の (`z` コマンドの実行前の) スタックの深さをプッシュする。

## 例
### スタック全体の合計
これはレジスタ a  に格納されたマクロを再帰的に呼び出してスタック全体の合計を計算する。マクロの動作は、まずスタックの先頭 2 を足し合わせ (`+`)、スタックの深さが 1 より大きい場合は再帰する (`1z<a`) ものである。マクロ文直前の `0d` は一見必要ないように思えるがが、加算演算子がスタックの先頭 2 の要素を確実に取り出せることを保証するために必要である。
 1 2 4 8 16 100  # 加算したい数をスタックに積む
 0d[+z1**131** となる。

### ファイル中の dc コマンドの合計
ファイルの各行に記述された dc コマンドを実行し、その合計値を計算する。単なる数値は dc コマンドとして有効であるので、行ごとに記述された数値の合計を得ることもできる。

これも上の例と同様にレジスタ a に格納されたマクロを再帰的に呼び出して合計を計算している。
```console
$ cat file | dc -e '0d[?+z1<a]dsaxp'
```
`?` コマンドは標準入力から dc コマンドを読み込み、結果をスタックにプッシュする。ファイルの終端に達した場合はコマンドは読み込まれず、スタックには何もプッシュされない。
```console
$ { echo "5"; echo "7"; } | dc -e '0d[?+z1<a]dsaxp'
```
この結果は `'''12'''` となる。

入力の dc コマンドは複雑でも良い。
```console
$ { echo "3 5 *"; echo "4 3 *"; echo "5dd++"; } | dc -e '0d[?+z1<a]dsaxp'
```
この結果は (3\times5)+(4\times3)+(5+5+5) = 42 より `'''42'''` となる。

この手法を利用することの長所は、dc の演算は無限精度であるので、 AWK などの簡明な手法を用いる場合に起こりうるオーバーフローや精度落ちが発生しないことである。

対して短所もあり、空行 (技術的には要素をプッシュしない行) に遭遇するとループが停止すること、負値の符号 - を dc の負符号 `_` に置換する必要があることが挙げられる。dc の `?` には空行とファイル終端を見分けるきれいな方法が提供されていない。

### 単位変換
以下に示すのは、ワンライナーで書かれた較的簡単な単位変換プログラムの例である:
```console
$ dc -e '[[Enter a number (metres), or 0 to exit]psj]sh[q]sz[lhx?d0=z10k39.370079*.5+0k12~1/rn[ feet ]Pn[ inches]P10Pdx]dx'
```
この例はメートルで表された距離をフィートとインチに変換する。ユーザに入力を促し、適切な形式で変換結果を出力し、別の数値を変換するためにループしている。

### 最大公約数
以下に示すのは互除法を利用して最大公約数を求める例である:
```console
$ dc -e '??[dSarLa%d0<a]dsax+p'                  # 最短実装
$ dc -e '[a=]P?[b=]P?[dSarLa%d0<a]dsax+[GCD:]Pp' # 読みやすくしたもの
```


### 階乗
入力された値 n の階乗 n! = \prod_{k=1}^{n}{k} を計算する:
```console
$ dc -e '?[q]sQ[d1=Qd1-lFx*]dsFxp'
```


### Quine
dc にも quine が存在する。
```console
$ dc -e '[91Pn[dx]93Pn]dx'
$ dc -e '[91PP93P[dx]P]dx'
```


### すべての素数を求める

```console
$ echo '2p3p[dl!d2+s!%0=@l!l^!<#]s#[s/0ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x' | dc
```
このプログラムは Michel Charpentier によって書かれた、すべての素数を表示するプログラムである。このプログラムは次のように短縮でき、恐らくこれが最短であると思われる。
```console
$ echo '2p3p[dl!d2+s!%0=@l!l^!<#]s#[0*ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x' | dc
```


### 素因数分解
これもまた Michel Charpentier によって書かれた:
```console
$ dc -e '[n=]P?[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2'
```
短くすると:
```console
$ dc -e "[n=]P?[lfp/dlf%0=Fdvsr]sF[dsf]sJdvsr2sf[dlf%0=Flfdd2%+1+sflr<Jd1<M]dsMx"
```
より高速なものでは (200 bit の数 2^{200} - 1 で試すなら `2 200^1-` を入力する):
```console
$ dc -e "[n=]P?[lfp/dlf% 0=Fdvsr]sFdvsr2sfd2%0=F3sfd3%0=F5sf[dlf%0=Flfd4+sflr>M]sN[dlf%0=Flfd2+sflr>N]dsMx[p]sMd1<M"
```
これを更に高速化するには、定数へのアクセスをレジスタへのアクセスに置き換える:
```console
$ dc -e "[n=]P?[lfp/dlf%l0=Fdvsr]sF2s2dvsr2sf4s4d2%0=F3sfd3%0=F5sf[dlf%l0=Flfdl4+sflr>M]sN[dlf%l0=Flfdl2+sflr>N]dsMx[p]sMd1<M"
```


### Diffie–Hellman 鍵交換
より複雑な例では、Perl スクリプトに組み込まれている Diffie–Hellman 鍵交換がある。これは ITAR 議論のときにサイファーパンクたちの間で人気であった。このスクリプトは Unix ライクな OS にはどこにでもある Perl と dc だけで実行できる:
```perl
#!/usr/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines
($g, $e, $m) = @ARGV, $m || die "$0 gen exp mod\n";
print `echo "16dio1[d2%Sa2/d0<X+d*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p | dc`
```
これのコメント付きのバージョンは少しわかりやすく、ループや条件分岐、マクロから脱出するための `q` コマンドなどの使い方が示されている。GNU の dc では、以下のコード中でレジスタ X に格納されるマクロを使う代わりに `|` コマンドで冪剰余を演算できる。
```perl
#!/usr/bin/perl

my ($g, $e, $m) = map { "\U$_" } @ARGV;
die "$0 gen exp mod\n" unless $m;

print `echo $g $e $m | dc -e '
# Hex input and output
16dio
# Read m, e and g from stdin on one line
?SmSeSg

# Function z: return g * top of stack
[lg*]sz

# Function Q: remove the top of the stack and return 1
[sb1q]sQ

# Function X(e): recursively compute g^e % m
# It is the same as Sm^Lm%, but handles arbitrarily large exponents.
# Stack at entry: e
# Stack at exit: g^e % m
# Since e may be very large, this uses the property that g^e % m == 
#     if( e == 0 )
#         return 1
#     x = (g^(e/2)) ^ 2
#     if( e % 2 == 1 )
#         x *= g
#     return x %
[
    d 0=Q   # return 1 if e==0 (otherwise, stack: e)
    d 2% Sa # Store e%2 in a (stack: e)
    2/      # compute e/2
    lXx     # call X(e/2)
    d*      # compute X(e/2)^2
    La1=z   # multiply by g if e%2==1
    lm %    # compute (g^e) % m
] SX

le          # Load e from the register
lXx         # compute g^e % m
p           # Print the result
'`;
```


## 関連項目
* bc (UNIX)
* ヒューレット・パッカードの電卓
* スタックマシン

## 脚注・出典


## 外部リンク
* Debian GNU/Linux レポジトリの dc パッケージ
* dc(1) – Plan 9 Programmer's Manual, Volume 1
*Man page of DC – JM Project
*Bc for Windows  (dc を含む)
* dc の web 実装: http://dc.pr0.uk/