MS-DOS Batch

MS-DOS Batch

Paradigm(s)	imperative, unstructured, tree
Designed by	Microsoft
Appeared in	1981
Memory system	variables, CLI arguments
Dimensions	one-dimensional
Computational class	Turing complete (MS-DOS 2.00 and above), bounded-storage machine (prior to 2.00)
Major implementations	MS-DOS
Influenced by	CP/M
Influenced	Various
File extension(s)	.bat, (.cmd exclusive to NT Batch)

MS-DOS Batch is a scripting language intended for system setup and running programs in Micosoft's MS-DOS operating system, as well as PC-DOS, DR-DOS, and similar. MS-DOS's COMMAND.COM executable is able to run certain files as a list of DOS commands in order, with support for control flow. MS-DOS Batch is a subset of Batch, which is a family of languages produced by Microsoft and other companies for their command-line operating systems. MS-DOS Batch is differentiated from other Batch languages for its peculiarities and restricted nature when compared to e.g. Windows NT Batch.

Variants

MS-DOS had multiple releases between 1981 and 1994, with additional extensions for Windows 9x, but these extensions were not provided in standalone MS-DOS distributions. The various releases had different available commands and functionality.

Additionally, several MS-DOS compatible operating systems and MS-DOS emulators exist. The most notable for modern use are FreeDOS (operating system) and DOSBox (emulator). DOSBox is designed to run video games from the MS-DOS era, and supports a subset of MS-DOS 5.00's command line.

Peculiarities

An interesting feature, often considered a misgiving, of MS-DOS Batch as well as NT Batch, and similar, is the concept of variable variables. Since the COMMAND.COM interpreter expands variables in place and every time a line is encountered, a variable can be used to reference another. Consider the following.

set a=a
set b=b
set ptr=a
echo %a% %b%
set %ptr%=b
echo %a% %b%

In this example, the ptr variable is used to point to another variable, with the set expanding the variable into a causing a to be set, instead of ptr. Retrieving the underlying value of the pointer is easy through one expansion, however it is desirable to be able to expand the variable fully. NT Batch provides this ability through delayed expansion, which can be seen on Batch.

Other than the CLI arguments passed to a script when run, MS-DOS Batch provides no typical method of user input. MS-DOS does have a pause command, but this can only pause execution of the program until a user presses any button. User input could potentially be encoded as the user creating and deleting certain directories, with mkdir and if ERRORLEVEL used to determine if the directories were created or not. This, however, is unrealistic for use in DOS unless multitasking is used, which is exclusive to certain versions of MS-DOS 4 and above. MS-DOS 6 provides a choice command as an external command, and non-MS DOS variants like DR-DOS supported switch, both of which can be used to accept user input.

Computational class

Batch (as implemented in MS-DOS 2.00 and above, as well as DOSBox), are in the class of bounded-storage machines. With modification that would not break compatibility with existing scripts, MS-DOS Batch could be in the class of Turing complete machines. Additionally, MS-DOS 2.00 and above can be viewed as an unordered tree machine with unbounded breadth and depth. It is unclear how append_to would be implemented, but it is not needed as unbounded depth is sufficient.

Prior to MS-DOS 2.00, Batch is a bounded-storage machine, being equivalent to an unordered tree machine with a maximal depth of 0, and unbounded breadth. Since versions before MS-DOS 2.00 do not have the ability to emulate the append_to instruction, it can only access a bounded amount of files. invoke is conditional in MS-DOS Batch.

Proof via Post-tag machines

For this proof the following commands will be used:

:LABEL (label definition)
goto
if
set
shift

It is trivial to construct an infinite loop by using the :label and goto commands. Additionally, some control is offered by if in conjunction with set, we can assume that these together are productive, allowing us to construct conditional loops.

While many programs can be expressed with just the above commands, it is not immediately obvious how infinite memory can be addressed, as required by the definition of a Turing machine. This is where shift comes into play. Batch scripts are given a list of arguments, which are passed in from the command line. E.g. if a script is called with script.bat 1 2 3 4 the arguments it receives will be script.bat, 1, 2, 3, 4 with each element being assigned to a numeric variable, in this case 0, 1, 2, 3, and 4. The shift command shifts all arguments a script receives leftwards. In our example the arguments would then be 1, 2, 3, 4, with argument 0 (script.bat) being shifted off.

The shift therefore serves as a way to delete an element from the list of arguments. The use of variables with set allows us to preserve elements which are shifted off. Consider the following:

set args=
:rebuild
if "%1" == "" goto end
set args=%args% %1
shift
goto rebuild

:end

The above script repeatedly shifts off arguments, but before they are shifted off they are captured into the args variable. The variable is effectively a space separated list of arguments. With this construction, one can reverse an argument list, construct an argument list which excludes elements which are equal to some value, exclude elements at the beginning, or if used with reversal, exclude arguments at the end. For MS-DOS 2.x the following needs to be done in order to avoid empty variables:

if "%1" == "" goto noargs
set args=%1
shift
:rebuild
if "%1" == "" goto hasargs
set args=%args% %1
shift
goto rebuild

:noargs
example
goto end

:hasargs
example %args%

:end

MS-DOS Batch, like several other shell languages, allow for the use of variables to run commands. When a line is encountered, variables are expanded, then the line is evaluated and executed. We can use this to e.g. examine the first argument which is passed to a script and use it to conditionally execute one of a number of scripts in a directory, %1 arg1 arg2. By combining this with the script above (modified to start from argument 0) which rebuilds the argument list, we are able to wholly recreate the command line used to call the script, for an arbitrary number of arguments, %args%. Additionally, arbitrary extra arguments can be prepended or appended to the reconstructed list simply by adding them in the appropriate spot, %args% extra0 extra1.

With these concepts a Post tag system can be constructed. For a given rule a Batch script is created, named [symbol].bat where [symbol] is the symbol on the left hand side of the rule. The m parameter of the machine is encoded in a number of shift commands which occur immediately after assigning a variable with the value of %1. After the shifts, the argument list is rebuilt. Finally, the assigned variable is used to call into another Batch file, provided with the rebuilt arguments, with the production rules appended to the end. An example for the rule a -> bc in a 2-tag machine (script would be in a.bat):

set target=%1

shift
shift

:rebuild
if "%1" == "" goto end
set args=%args% %1
shift
goto rebuild

:end
%target% %args% b c

The machine would be started with a toplevel Batch script which determines the starting rule to follow. The toplevel script would not perform any shifts, except to reconstruct the arguments. The pattern above can be modified with the modifications required for MS-DOS 2.x as illustrated previously.

Since this scheme can encode any Post tag machine of n rules into n + 1 Batch scripts, and any Turing machine can be encoded in a Post tag machine, MS-DOS Batch is Turing complete. However, MS-DOS has several limitations placed on it. For instance, environment variables can only be up to a certain number of characters long. This means that the amount of memory available to the tag machine is limited, so this construction is only in the class of bounded storage machines.

External resources

• A Wikipedia article about batch files