dc

From Esolang
Jump to navigation Jump to search

The unix dc(1) command, this is the esoteric language that "made it big". Originally written in assembler for Unix V1 it was translated to C for Version 7 Unix and paired with a wrapper bc(1) that changed it from a desktop calculator (like the HP-48) to a better calculator for mere mortals. This wrapper meant it became frequently used on many Unix versions despite many users never seeing it.

All numbers are unbounded and may have a specified number of digits in the fractional part.

Unix V7

Standard commands

This table documents the standard commands as they appeared in the V7 Unix version.

Command Description
Whitespace Official whitespace characters are No-op instructions
Number A number is a string of digits, it is pushed onto the main stack. Negative numbers are preceded by the '_' character. The default input base is decimal.
[ ... ] Pushes the bracketed string onto the main stack. There can be *properly nested* brackets within the string
+ - / * The top two arguments are taken from the stack and the operator applied, the result is pushed back onto the stack.
% The remainder of the top two items on the stack replaces them
^ The exponentiation of the top two items on the stack replaces them, any fractional part in the exponent is ignored.
v The top of stack is popped and replaced by it's square root
sX The top of stack is popped and stored in register X, "X" may be any character.
SX The top of stack is popped and pushed onto stack X, "X" may be any character.
lX (lowercase ell) The value in register X is copied and pushed onto the stack.
LX The top of stack X is popped and pushed onto the main stack.
d Duplicate the top of the main stack
c The main stack is cleared; all values popped and discarded.
p The top of stack is printed, followed by a newline, but NOT popped; the stack remains unchanged.
P The top of stack is popped and converted into a string which is then printed.
f All values on the stack are printed; the stack remains unchanged.
x The top of stack is popped and converted into a string, the string is then executed. Once the execution of the string finishes the command after the "x" is executed. Note: tail recursion is expected.
>X <X =X The top two items on the main stack are popped and compared with the relation. If true the register X is executed as a string.
!>X !<X !=X The top two items on the main stack are popped and compared with the relation. If false the register X is executed as a string.
z The number of items on the main stack is pushed onto the stack.
Z The length of the item on the top of the stack replaces it.
X Replaces the number on top of the stack with it's scale factor
? A line of text is taken from the input and executed.
q The execution of the current string and the string it was executed from (if any) are terminated.
Q A value is popped from the stack and that many nested string executions are terminated.
:X A value is popped from the stack and used to index array X, the next value is then popped from the stack and stored in the referenced element.
;X A value is popped from the stack and used to index array X, the referenced element is copied and pushed onto the stack.
! Run the rest of the line as an OS command.

State commands

These commands change global state variables in the V7 Unix version's interpreter.

Command Description
i A value is popped from the stack and used for the input radix. Valid input digits are "0123456789ABCDEF" so only bases 2..16 are reasonable, however, changing the base does not limit the digits available. This means the sequence " Ai" will always return to decimal.
I The current input radix is pushed onto the stack
o A value is popped from the stack and used for the output radix. Bases 2..16 are displayed using normal digit form, bases of 17 and above are displayed using space separated stings of decimal digits. This makes "100000o" display the values in decimal with a space every 5 digits.
O The current output radix is pushed onto the stack
k A value is popped from the stack and used for the current "skale factor". This is the number of decimal places after the point for input and calculated values.
K The current "skale factor" is pushed onto the stack

Additional commands

These commands are common to most current versions of dc(1).

Command Description
# Treat the rest of the line as a comment.
n Pops the top of stack and prints it without a newline.
a The top of stack is converted to a string (numbers are converted to a byte) and the first byte is pushed as a string.
r Swaps the top two values on the stack.

GNU Extensions

This command is specific to the GNU version

Command Description
| Pops three values and computes a modular exponentiation. Similar to "Sm^Lm%"

BSD Extensions

These commands are specific to the BSD version

Command Description
G EQ - Two values are popped from the stack and a zero is pushed if they are different, a one if identical.
( The top two numbers are popped from the stack. If the TOS is greater than or equal to the NOS a zero is pushed otherwise a one is pushed.
{ The top two numbers are popped from the stack. If the TOS is greater than to the NOS a zero is pushed otherwise a one is pushed.
N Not command: If the TOS is zero it is replace with one, otherwise it's set to zero.
R Remove. The top if stack is popped and discarded.
<xey >xey =xey !<xey !>xey !=xey Extensions to the conditional operations; the 'e' command specifies an 'else' macro that is run if the condition is reversed.
J A value is popped from the stack and that many command nesting levels are popped. The code is then skipped until an 'M' commands is found.
M Mark the position jumped to by the 'J' commands. Otherwise a NOP.

Named stacks

The same variables are referenced by all the "S s L l : ;" commands, this gives some interesting effects.

The named variables are initially empty. The "s" command will store a value onto the top of stack, creating the TOS if it doesn't exist and converting it to a simple value if it is an array. The "S" command will add a new TOS to the named stack, if there is a value it will be pushed to the next on stack. The "l" command will read the current top of the named stack, if there isn't one it will return zero and not give an error. The "L" command will act like the "l" command but instead of copying the TOS it moves it to the main stack and errors if it doesn't exist.

The ":" command will ensure the current top of the named stack is an array (creating or converting it if necessary) and then will set the element as requested. The ";" operator should only be used against stacks where the TOS is known to be an array. Setting the named stack with "s" will discard the array, pushing a new value with "S" will hide the current TOS even if it's an array and "L" will correctly reveal it again. This gives Dc multiple unbounded stacks of unbounded arrays with unbounded integers (In theory). All other operations with arrays are undefined; copying or moving an array to the main stack is likely to cause the interpreter to crash.

Computational class

There are at least five essentially different known proofs that dc is Turing-complete:

  • Because dc contains "duplicate", "push string", and "eval" instructions, it embeds the (Turing-complete) ()^: fragment of Underload.
  • The S and L commands provide multiple independent stacks, allowing for a stack-based data storage. (To complete the proof, it's also required to show that a full set of control flow is available, most simply by using an array as a lookup table and implementing StackFlow.)
  • It's also possible to use a single array as data storage for a Turing-completeness demonstration, e.g. by implementing the I/D machine.
I/D Machine DC Translation Note
I lp;a1+lp:a Note the 1 is a run length count (in decimal)
D lp;asp
  • Because dc uses bignums, you can implement a Minsky machine more or less directly.
  • Finally the family of Turing machines that constitute Brainfuck can be translated directly.
This translation uses bignum cells, byte cells can be implemented using 256 %
BF Command DC Translation
Init 0sp[q]sq
> lp1+sp
< lp1-sp
+ lp;a1+lp:a
- lp;a1-lp:a
[ [lp;a0=q
] lbx]dSbxLbs.
. Not required, but usually works lp;aaP
, Not required
  • The 1 in the commands <>+- is a run length count (in decimal).
  • ASCII output can be done using the Unix V7 implementation by using a long list of literal strings for each allowed value.
  • Input is only possible using the ? command which needs character input to be translated into numbers.

Examples

This prints the numbers from one factorial to 20 factorial in base 11.

[la1+dsa*pla20>y]sy 0sa1 11o lyx

This prints the first 20 Fibonacci numbers:

1d[prdk+KdZ5>x]dsxx