Original author(s) | Lorinda Cherry, Robert Morris (AT&T Bell Laboratories) |
---|---|
Developer(s) | Various open-source and commercial developers |
Written in | B |
Operating system | Unix, Unix-like, Plan 9 |
Platform | Cross-platform |
Type | Command |
dc (desk calculator) is a cross-platform reverse-Polish calculator which supports arbitrary-precision arithmetic. [1] It was written by Lorinda Cherry and Robert Morris at Bell Labs. [2] It is one of the oldest Unix utilities, preceding even the invention of the C programming language. Like other utilities of that vintage, it has a powerful set of features but terse syntax. [3] [4] Traditionally, the bc calculator program (with infix notation) was implemented on top of dc.
This article provides some examples in an attempt to give a general flavour of the language; for a complete list of commands and syntax, one should consult the man page for one's specific implementation.
dc is the oldest surviving Unix language program. When its home Bell Labs received a PDP-11, dc—written in B —was the first language to run on the new computer, even before an assembler. [2] Ken Thompson has opined that dc was the very first program written on the machine. [5]
To multiply four and five in dc (note that most of the whitespace is optional):
$ cat<<EOF>cal.txt 4 5 *pEOF$ dccal.txt 20$
The results are also available from the commands:
$ echo"4 5 * p"|dc
or
$ dc- 4 5*pq20$ dc 4 5 *p20q$ dc-e'4 5 * p'
This translates into "push four and five onto the stack, then, with the multiplication operator, pop two elements from the stack, multiply them and push the result onto the stack." Then the p
command is used to examine (print out to the screen) the top element on the stack. The q
command quits the invoked instance of dc. Note that numbers must be spaced from each other even as some operators need not be.
The arithmetic precision is changed with the command k
, which sets the number of fractional digits (the number of digits following the point) to be used for arithmetic operations. Since the default precision is zero, this sequence of commands produces 0
as a result:
2 3 / p
By adjusting the precision with k
, an arbitrary number of decimal places can be produced. This command sequence outputs .66666
.
5 k 2 3 / p
To evaluate : (v
computes the square root of the top of the stack and _
is used to input a negative number):
12 _3 4 ^ + 11 / v 22 - p
To swap the top two elements of the stack, use the r
command. To duplicate the top element, use the d
command.
To read a line from stdin, use the ?
command. This evaluates the line as if it were a dc command, and so it is necessary that it be syntactically correct and presents a potential security problem because the !
dc command enables arbitrary command execution.
As mentioned above, p
prints the top of the stack with a newline after it. n
pops the top of the stack and prints it without a trailing newline. f
prints the entire stack with one entry per line.
dc also supports arbitrary input and output radices. The i
command pops the top of the stack and uses it for the input base. Hex digits must be in upper case to avoid collisions with dc commands and are limited to A-F. The o
command does the same for the output base, but keep in mind that the input base affects the parsing of every numeric value afterwards so it is usually advisable to set the output base first. Therefore 10o
sets the output radix to the current input radix, but generally not to 10 (ten). Nevertheless Ao
resets the output base to 10 (ten), regardless of the input base. To read the values, the K
, I
and O
commands push the current precision, input radix and output radix on to the top of the stack.
As an example, to convert from hex to binary:
$ echo16i2oDEADBEEFp|dc 11011110101011011011111011101111
In addition to these basic arithmetic and stack operations, dc includes support for macros, conditionals and storing of results for later retrieval.
The mechanism underlying macros and conditionals is the register, which in dc is a storage location with a single character name which can be stored to and retrieved from: sc
pops the top of the stack and stores it in register c, and lc
pushes the value of register c onto the stack. For example:
3 sc 4 lc * p
Registers can also be treated as secondary stacks, so values can be pushed and popped between them and the main stack using the S
and L
commands.
String values are enclosed in [
and ]
characters and may be pushed onto the stack and stored in registers. The a
command converts the low order byte of the numeric value into an ASCII character, or if the top of the stack is a string it replaces it with the first character of the string. There are no ways to build up strings or perform string manipulation other than executing it with the x
command, or printing it with the P
command.
The #
character begins a comment to the end of the line.
Macros are then implemented by allowing registers and stack entries to be strings as well as numbers. A string can be printed, but it can also be executed (i.e. processed as a sequence of dc commands). So for instance we can store a macro to add one and then multiply by 2 into register m:
[1 + 2 *] sm
and then (using the x
command which executes the top of the stack) we can use it like this:
3 lm x p
Finally, we can use this macro mechanism to provide conditionals. The command =r
pops two values from the stack, and executes the macro stored in register r
only if they are equal. So this prints the string equal
only if the top two values on the stack are of equal value:
[[equal]p] sm 5 5 =m
Other conditionals are >
, !>
, <
, !<
, !=
, which execute the specified macro if the top two values on the stack are greater, less than or equal to ("not greater"), less than, greater than or equal to ("not less than"), and not equals, respectively. Note that the order of the operands in inequality comparisons is the opposite of the order for arithmetic; 5 3 - evaluates to 5 - 3 = 2
, but 5 3 <t runs the contents of the t register because 3 < 5
.
Looping is then possible by defining a macro which (conditionally) reinvokes itself. A simple factorial of the top of the stack might be implemented as:
# F(x): return x! # if x-1 > 1 # return x * F(x-1) # otherwise # return x [d1-d1<F*]dsFxp
The 1Q
command exits from a macro, allowing an early return. q
quits from two levels of macros (and dc itself if there are less than two levels on the call stack). z
pushes the current stack depth before the z
operation.
This is implemented with a macro stored in register a
which conditionally calls itself, performing an addition each time, until only one value remains on the stack. The z
operator is used to push the number of entries in the stack onto the stack. The comparison operator >
pops two values off the stack in making the comparison.
dc-e"1 2 4 8 16 100 0d[+z1<a]dsaxp"
And the result is 131.
A bare number is a valid dc expression, so this can be used to sum a file where each line contains a single number.
This is again implemented with a macro stored in register a
which conditionally calls itself, performing an addition each time, until only one value remains on the stack.
dc-e"0d[?+z1<a]dsaxp"<file
The ?
operator reads another command from the input stream. If the input line contains a decimal number, that value is added to the stack. When the input file reaches end of file, the command is null, and no value is added to the stack.
{echo"5";echo"7";}|dc-e"0d[?+z1<a]dsaxp"
And the result is 12.
The input lines can also be complex dc commands.
{echo"3 5 *";echo"4 3 *";echo"5dd++";}|dc-e"0d[?+z1<a]dsaxp"
And the result is 42.
Note that since dc supports arbitrary precision, there is no concern about numeric overflow or loss of precision, no matter how many lines the input stream contains, unlike a similarly concise solution in AWK.
Downsides of this solution are: the loop stops on encountering a blank line in the input stream (technically, any input line which does not add at least one numeric value to the stack); and, for handling negative numbers, leading instances of '-' to denote a negative sign must be change to '_' in the input stream, because of dc's nonstandard negative sign. The ?
operator in dc does not provide a clean way to discern reading a blank line from reading end of file.
As an example of a relatively simple program in dc, this command (in 1 line):
dc-e'[[Enter a number (metres), or 0 to exit]PAP]sh[q]sz[lhx?d0=zAk.0254/.5+0kC~1/rn[ feet ]Pn[ inches]PAPdx]dx'
converts distances from metres to feet and inches; the bulk of it is concerned with prompting for input, printing output in a suitable format and looping around to convert another number.
As an example, here is an implementation of the Euclidean algorithm to find the GCD:
dc-e'??[dSarLa%d0<a]dsax+p'# shortest dc-e'[a=]P?[b=]P?[dSarLa%d0<a]dsax+[GCD:]Pp'# easier-to-read version
Computing the factorial of an input value,
dc-e'?[q]sQ[d1=Qd1-lFx*]dsFxp'
There exist also quines in the programming language dc; programs that produce its source code as output.
dc-e'[91Pn[dx]93Pn]dx' dc-e'[91PP93P[dx]P]dx'
echo'2p3p[dl!d2+s!%0=@l!l^!<#]s#[s/0ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x'|dc
This program was written by Michel Charpentier. It outputs the sequence of prime numbers. Note that shorter implementation is possible, which reads fourteen symbols less.
echo'2p3p[pq]s$[l!2+ds!l^<$dl!%0<#]s#[+dvs^1s!l#x2l.x]ds.x'|dc
dc-e'[n=]P?[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2'
This program was also written by Michel Charpentier. [6]
There is a shorter
dc-e"[n=]P?[lfp/dlf%0=Fdvsr]sF[dsf]sJdvsr2sf[dlf%0=Flfdd2%+1+sflr<Jd1<M]dsMx"
and a faster solution (try with the 200-bit number 2200-1 (input 2 200^1-
)
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"
Note that the latter can be sped up even more, if the access to a constant is replaced by a register access.
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"
An implementation of the Chudnovsky algorithm in the programming language dc. The program will print better and better approximations as it runs. But as pi is a transcendental number, the program will continue until interrupted or resource exhaustion of the machine it is run on.
dc-e'_640320[0ksslk3^16lkd12+sk*-lm*lhd1+sh3^/smlxlj*sxll545140134+dsllm*lxlnk/ls+dls!=P]sP3^sj7sn[6sk1ddshsxsm13591409dsllPx10005v426880*ls/K3-k1/pcln14+snlMx]dsMx'
A fast divide and conquer implementation of the same formula that doubles in size each iteration. It evaluates a finite number if sums as an exact rational number and only performs one large division and square root per iteration. It is fast, but will still quickly slow down as the size of the fraction increases.
dc-e'1Sk1SR13591409dSBSP426880dSQ4/3^9*SC[0r-]s-[lkE*1-k10005vlQ*lP/nAan0k]dSox[Lkd1+Skdd1+Sk3^lC*SQ2*1-d3*d*4-*dSR545140134LB+dSB*lk2%0=-SP]dszx[LRLRdLP*LPLQdLQ*SQ*+SP*SR]sc[d1-d0<yd0<yd0=z0=zlcx]sy0[lcxlox1+lyxllx]dslx'
A more complex example of dc use embedded in a Perl script performs a Diffie–Hellman key exchange. This was popular as a signature block among cypherpunks during the ITAR debates, where the short script could be run with only Perl and dc, ubiquitous programs on Unix-like operating systems: [7]
#!/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`
A commented version is slightly easier to understand and shows how to use loops, conditionals, and the q
command to return from a macro. With the GNU version of dc, the |
command can be used to do arbitrary precision modular exponentiation without needing to write the X function.
#!/usr/bin/perlmy($g,$e,$m)=map{"\U$_"}@ARGV;die"$0 gen exp mod\n"unless$m;print`echo $g $e $m | dc -e '# Hex input and output16dio# 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] SXle # Load e from the registerlXx # compute g^e % mp # Print the result'`;
If the environment variable DC_LINE_LENGTH exists and contains an integer that is greater than 1 and less than , the output of number digits (according to the output base) will be restricted to this value, inserting thereafter backslashes and newlines. The default line length is 70. The special value of 0 disables line breaks.
Forth is a stack-oriented programming language and interactive integrated development environment designed by Charles H. "Chuck" Moore and first used by other programmers in 1970. Although not an acronym, the language's name in its early years was often spelled in all capital letters as FORTH. The FORTH-79 and FORTH-83 implementations, which were not written by Moore, became de facto standards, and an official technical standard of the language was published in 1994 as ANS Forth. A wide range of Forth derivatives existed before and after ANS Forth. The free and open-source software Gforth implementation is actively maintained, as are several commercially supported systems.
sed is a Unix utility that parses and transforms text, using a simple, compact programming language. It was developed from 1973 to 1974 by Lee E. McMahon of Bell Labs, and is available today for most operating systems. sed was based on the scripting features of the interactive editor ed and the earlier qed. It was one of the earliest tools to support regular expressions, and remains in use for text processing, most notably with the substitution command. Popular alternative tools for plaintext string manipulation and "stream editing" include AWK and Perl.
troff, short for "typesetter roff", is the major component of a document processing system developed by Bell Labs for the Unix operating system. troff and the related nroff were both developed from the original roff.
In electronics, a multiplexer, also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The selection is directed by a separate set of digital inputs known as select lines. A multiplexer of inputs has select lines, which are used to select which input line to send to the output.
In logic, mathematics, and computer science, arity is the number of arguments or operands taken by a function, operation or relation. In mathematics, arity may also be called rank, but this word can have many other meanings. In logic and philosophy, arity may also be called adicity and degree. In linguistics, it is usually named valency.
In software development, Make is a command-line interface software tool that performs actions ordered by configured dependencies as defined in a configuration file called a makefile. It is commonly used for build automation to build executable code from source code. But, not limited to building, Make can perform any operation available via the operating system shell.
The C preprocessor is the macro preprocessor for several computer programming languages, such as C, Objective-C, C++, and a variety of Fortran languages. The preprocessor provides inclusion of header files, macro expansions, conditional compilation, and line control.
Quantization, in mathematics and digital signal processing, is the process of mapping input values from a large set to output values in a (countable) smaller set, often with a finite number of elements. Rounding and truncation are typical examples of quantization processes. Quantization is involved to some degree in nearly all digital signal processing, as the process of representing a signal in digital form ordinarily involves rounding. Quantization also forms the core of essentially all lossy compression algorithms.
printf is a C standard library function that formats text and writes it to standard output.
m4 is a general-purpose macro processor included in most Unix-like operating systems, and is a component of the POSIX standard.
bc, for basic calculator, is "an arbitrary-precision calculator language" with syntax similar to the C programming language. bc is typically used as either a mathematical scripting language or as an interactive mathematical shell.
Code injection is a class of computer security exploits in which a vulnerable computer program is tricked into misinterpreting external data as part of its code. An attacker thereby introduces code into the program and changes the course of its execution. The result of successful code injection can be disastrous, for example, by allowing computer viruses or computer worms to propagate.
FOCAL is an interactive interpreted programming language based on JOSS and mostly used on Digital Equipment Corporation (DEC) Programmed Data Processor (PDP) series machines.
Mathomatic is a free, portable, general-purpose computer algebra system (CAS) that can symbolically solve, simplify, combine and compare algebraic equations, and can perform complex number, modular, and polynomial arithmetic, along with standard arithmetic. It can perform symbolic calculus (derivative, extrema, Taylor series, and polynomial integration and Laplace transforms), numerical integration, and can handle all elementary algebra except logarithms. Trigonometric functions can be entered and manipulated using complex exponentials, with the GNU m4 preprocessor. Not currently implemented are general functions such as f(x), arbitrary-precision and interval arithmetic, as well as matrices.
scanf, short for scan formatted, is a C standard library function that reads and parses text from standard input.
The Mouse programming language is a small computer programming language developed by Dr. Peter Grogono in the late 1970s and early 1980s. It was developed as an extension of an earlier language called MUSYS, which was used to control digital and analog devices in an electronic music studio.
The PDP-11 architecture is a 16-bit CISC instruction set architecture (ISA) developed by Digital Equipment Corporation (DEC). It is implemented by central processing units (CPUs) and microprocessors used in PDP-11 minicomputers. It was in wide use during the 1970s, but was eventually overshadowed by the more powerful VAX architecture in the 1980s.
Rexx is a programming language that can be interpreted or compiled. It was developed at IBM by Mike Cowlishaw. It is a structured, high-level programming language designed for ease of learning and reading. Proprietary and open source Rexx interpreters exist for a wide range of computing platforms; compilers exist for IBM mainframe computers.
In Unix and Unix-like operating systems, printf is a shell builtin that formats and outputs text like the same-named C function.
jq is a very high-level lexically scoped functional programming language in which every JSON value is a constant. jq supports backtracking and managing indefinitely long streams of JSON data. It is related to the Icon and Haskell programming languages. The language supports a namespace-based module system and has some support for closures. In particular, functions and functional expressions can be used as parameters of other functions.