4 -- Command Language Interpreters

22C:112 Notes, Spring 2008

Part of the 22C:112, Operating Systems Notes
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

A Simple Operating System

Since the 1960's, customers have demanded a minimal suite of system software when they buy even the smallest computer systems. The bare minimum consists of a text editor, an assembler, a linker, a loader, a set of subroutines for doing input-output, and a command language for directing the operation of the various programs. When the subroutine library included support for a disk-based file system, such an operating system has frequently been referred to as a disk operating system or DOS. There have been many DOS systems, all unrelated to each other.

These software components are sometimes lumped together as the operating system, it is generally useful to differentiate between the system support utilities such as editors and language processors, on the one hand, and the run-time services offered by the operating system and command language on the other hand. The former are used in preparing a program to run, while the latter are used to run programs once they have been prepared. Throughout, we will use the term operating system to refer to the latter.

The minimal operating system to be discussed here is typical of the single-user systems found on most early machines. These include the mainframes of the 1950's, the minicomputers of the 1960's, and the microcomputers of the 1970's. Few general purpose computers in common use today have such primitive operating systems, but most of today's operating systems can be traced back to such systems.

The term general purpose is, of course, essential to the above paragraph. Special purpose computer systems are frequently sold with no operating system at all. Embedded computer systems, those that become part of some large product, whether a TV remote control, a home appliance, an airplane or a laboratory instrument frequently execute fixed programs where the line between system and application is completely blurred. The programs for such systems are frequently developed on general purpose computers and burned into read-only memory as part of the manufacturing process.

Although the particular set of peripheral devices attached to the computer is not of critical importance in this discussion, it is useful to consider a system with the following peripherals: A keyboard for user input, a display screen for output, a printer, and a number of storage devices for sequential files. On a modern system, these sequential files would usually be stored on one or more disk drives, but disk drives are complicated. In order to build a minimal system very quickly, we are better off talking of extremely simple I/O devices like the cassette tapes that were widely used with the first generation of personal computers in the 1970's or the open-reel magnetic tape drives of first-generation mainframes. Here is a picture of such a system.

                                   ________
 __________                     --| tape 1 |
|          |                   |  |________|
| display  |      __________   |   ________
|  screen  |-----|          |--   | tape 2 |
|__________|     | computer |-----|________|
               --|          |--
 __________   |  |__________|  |   _________ 
| keyboard |--                  --| printer |
|__________|                      |_________|

A dismayingly simple computer system.

In the early 1950s, such a system would have cost millions and occupied a large machine room, while by the mid 1980s, such a system would only cost a few hundred dollars. The operating system requirements for such a simple computer system do not depend on the tape technology being used, and they do not depend on whether the computer has a microprocessor or vacuum tubes in its heart.

The tape drives used by computers of the 1950s and 1960s used half-inch wide magnetic tape, wound on reels that were about a foot in diameter. The drives themselves were the size of a refrigerator, and large computer centers frequently had tape drives lined up along an entire wall of the center, dwarfing the CPU. It is no wonder that cartoonists of the 1950's and 1960's frequently focused on these gigantic tape drives as a visual symbol of computers and computer technology.

System Structure

The run-time system services provided by a single-user operating system for a machine such as that illustrated in Figure 8.1 would typically allow for the following operations: input from any device other than the display screen, output to any device other than the keyboard, rewinding any tape drive, and loading a program from any tape drive. These services can be packaged in any of a number of ways, but since the loader service itself requires use of the input service, it is reasonable to think in terms of the hierarchic design shown below.

 _________________________________________
|                                         |
|           the command language          |
|                interpreter              |
|                                         |
|          _______\calls/_______          |
|         |                     |         |
|         |     application     |         |
|         |      programs       |         |
|         |                     |         |
|_\calls/_|_\calls/_            |         |
|                   |           |         |
|      loader       |           |         |
|                   |           |         |
|______\calls/______|__\calls/__|_\calls/_|
|                                         |
|           input-output library          |
|_________________________________________|
A hierarchic design for a simple operating system.

The hierarchy shown in Figure 8.2 can be thought of in terms of subroutine call relationships, with the calling system component on top and the called component on the bottom. So, the input-output library provides services called by all other parts of the system, and the command language interpreter calls input-output library services to read the command language, it calls the loader to load the programs it is commanded to load, and it then calls the programs themselves. Application programs call input-output library routines, and if they include overlays, they also call the loader.

When a computer system has no protection mechanisms, that is, mechanisms to prevent application code from corrupting the operating system, calls from application code to system services and calls from the command language interpreter to user code are all generally done using the same subroutine call instructions that one part of an appliction might use to call another part of the same application.

On large computers with protection mechanisms, normal subroutine calls are only used to call procedures or functions within the same protection domain, while calls that cross domain boundaries frequently use entirely different mechanisms. This change of mechanism involves no change in the user's intent, but is only required in order to prevent unauthorized accesses from either calling or called routine to code or data belonging to the other. Because of this, we will emphatically avoid mention of protection and treat all system services as if they were simple subroutines that can be called by the same mechanisms used to call parts of user programs.

A Set of Input/Output System Services

In many primitive systems, a different subroutine was provided for each system service. As a result, a user wishing to change a program to read from tape drive A to tape drive B would be forced to rewrite the program. In a remarkable number of cases, different devices actually used different character sets, so it was necessary to change the code that processed the input or generated the output when the change was made from outputting to the printer instead of outputting to the display screen or when a change was made from keyboard input to input from tape. Even in the mid 1950's, these extreme cases were the subject of ridicule, and programmers strove to create uniform interface standards.

The FORTRAN language, developed in the mid 1950's by John Baccus at IBM, provides for a uniform input-output interface by addressing all input-output operations to abstract input-output units. All a programmer needs to do in order to change the unit being operated on is change the unit number. On a very crude system, unit 1 might be the keyboard, unit 2 might be the display, unit 3 might be the printer, and units 4 and up might be tape drives.

Baccus did not know anything about abstract data types; that concept was only formalized in the late 1960's, but despite this, it is clear that each input-output unit in Baccus's model is an instance of an abstract data type. To use modern terminology, each input-output unit is an instance of a polymorphic class. Instances of this class support the methods read and write (plus some others), and the class is polymorphic because the implementations of these methods differs for each device. For example, the read from a keyboard is done by entirely different code than the read from a tape drive.

Baccus's use of numerical unit numbers suggests that, in the abstract, he required the programmer to view the available input-output units as being arranged in an array. Named devices would have been nice, but only after the mid 1960's did operating systems routinly support symbolic device names, and as file systems became common, symbolic file names. Named devices and files requires that the system include a symbol table to relate names to devices or files; this might be called the device table, or on later systems, the directory of the file system.

If cost was no object, we might be tempted to invent a system input-output service along the lines of put(d,c) where d is a symbolic device name, and c is a character to be output to that device. The problem with this idea is that it suggests that we have to look up the device by its symbolic name once for each character output to that device, and we do not generally want to pay the price of so many lookup operations.

In order to avoid excessive device-table lookup operations, we typically introduce a new operation, open that takes a symbolic file or device name and returns a descriptor for that file or device. In crude systems, the descriptor is nothing more than an old FORTRAN-style unit number, but in an abstract sense, an I/O descriptor is always the handle on an object that represents an I/O device that is capable of performing the basic I/O operations, usually given names such as read, write and rewind (the classic FORTRAN names) or put, get and seek (in the C/Unix tradition).

The opened file descriptor can be described as an abstract data type, as in the following figure:

Sets needed

S -- the set of symbolic file names
F -- the set of file descriptors
C -- the set of characters

Functions on the sets

open: S --> F (given a symbolic file name, returns an open file)
rewind: F --> F
read: F --> F x C
write: F x C --> F

Informal descriptions

open(f,s) or f = open(s)
sets f to refer to the device with the symbolic name s; usually, this involves an implicit rewind.

rewind(f) or f.rewind
positions f at the start of file.

read(f,c) or c = f.read
reads the character c from f, updating the state of f to reflect this.

write(f,c) or f.write(c)
writes the character c to f, updating the state of f to reflect this.

The file variable abstract data type.

In the above, two different concrete notations are shown for the calls to the read, write and rewind operations. The lefthand notation is a purely procedural notation, where read, write and rewind operate through side effects on their parameters; the righthand notation is an object-oriented notation where the operations are the methods of the class, and a device descriptor is a handle for objects in this class. Aside from the question of programming language syntax, these views are equivalent.

The input-output operations suggested in Figure 8.3 are sufficient for most purposes, but they are hardly convenient! If these are the only available services, programmers would be required to do all input-output one character at a time, and this poses both conceptual and practical problems. Most systems therefore provide additional services such as those suggested below:

readblock(f,b,i) or f.readblock( b, i )
reads a block of i bytes from f to buffer b.

writeblock(f,b,i) or f.writeblock( b, i )
writes a block of i bytes to f from buffer b.

readline(f,b,i) or f.readline( b, i )
read a line of up to i bytes from f to buffer b. if less than i bytes were read, an line terminator character will follow the last character of input.

writeline(f,b,i) or f.writeline( b, i )
write a line of up to i bytes to f from buffer b. if the buffer contains a line terminator character, the write will stop before writing i characters, and the last character output will always be a line terminator.

Additional input-output routines.

In an object-oriented world, we can view the additional services shown in here as being provided by a class-extension to the basic set of services, but this presumes that all devices support the basic character sequential services as primitives, and this is not true! Devices such as the keyboard do indeed support character sequential input, and low-end printers support character sequential output. Most tape formats, however, are implemented as block sequential formats, with hardware interfaces that directly support operations analogous to readblock and writeblock. On these, the character oriented services would be logically an extension of the block oriented services!

Even when our underlying devices are character sequential, it is frequently a good idea to provide block-oriented I/O services as primitives on high performance devices. The reason for this is twofold. First, the overhead of one subroutine call per character being output can be significant, and second, some devices only perform well if there is a guarantee that data will arrive at a uniform rate. For example, consider a high-speed tape reader. To read one character, the device must start the tape moving, read, and then stop the tape. To read a block of characters, the tape can be started and left moving for the entire length of the block. As a result, using character oriented I/O to read a block of 100 characters might end up starting and stopping the tape 100 times, while using a block-oriented approach would only have one start and one stop. Mechanical start and stop operations can be very slow compared to the electronic operations of actually reading or writing a byte of data!

Note that the typical input-output primitives presented in here are significantly different from the primitives of high level languages such as FORTRAN, Pascal, or C, in that no provisions are made for data format conversions. Most programming languages include an intermediate software layer between the operating system's input-output routines and the user for format conversion between textual representations of values and their internal representations. Thus, FORTRAN has its FORMAT statement, C has fprintf() and fscanf(), and object oriented languages tend to include standard methods for each predefined class to perform such conversions. However it is presented to users, format conversion layer of a language can be dismayingly complicated.

Protection mechanisms can complicate the way in which a user views a file variable or open file descriptor, since the contents of this variable are, in a sense, the private property of the file system. In an unprotected environment, file variables can be records (or pointers to records) containing whatever information is necessary to access a particular device. In a protected environment, the system must be able to guarantee that no user can misuse the information in the file variable, even if the user is working in a language like C or assembly language where the language does not enforce type integrety.

The protection mechanisms of operating systems frequently protect the open file variables or file descriptors by removing this information from the address space of the user program. Instead of giving the user a pointer to the data structure describing an open file, the user is given a small integer that is the index into a small array of open file descriptions, where there is one array entry per file that user has open. This exactly matches the old Fortran model, with open files described by unit numbers, and it is, in fact, the model that is used in Unix.

On some systems, notably the various flavors of OS on the IBM 360/370/390 family of mainframes (now called enterprise servers) slots in this table have symbolic names; typical (and still widely used) names are SYSIN, SYSPRINT, and SYSPUNCH (nowdays, rarely applied to actual printers and card punches, but named after those historic devices). Since the table for any user is small, the cost of a linear search for a table entry is small enough that the open file table can be searched each time the user manipulates a file.

Some other older systems provide a radically different set of primitives; an extreme alternative is to have a single input-output system service which accepts a file control block as a parameter. This block is a record listing such things as the buffer address and size, the direction of the transfer, the type of the transfer (line or block), whether the file should be rewound before the transfer, the name of the file to be used, and space for the system to fill in additional information it may need for its own purposes. Typically, on the first call to this general input-output routine, the system looks up the file name in the directory and the system space in the block is initialized to contain the information which would otherwise reside in an opened file descriptor. All subsequent calls will be fast because they do not need to look up the file name. The risk in such systems is that the user might accidentally corrupt some of the system information in the file control block.

Loader System Services

The smallest of systems sometimes offer only an absolute (non-relocating) loader, thus forcing all application code to be written with knowledge of where in memory it will eventually be loaded. Since relocating loaders are only slightly more complex than absolute loaders, most systems provide a relocating loader that can load applications in any available memory. Some larger systems provide, as a system service, a linking loader, but linking loaders are usually not system services, but must first be loaded themselves before they are run.

A typical loader must be passed the name of the file to be loaded or an already open file variable from which the object code should be read. If the loader can handle relocation, it must also be passed the initial relocation base, and in that case, it is useful to have the loader return the address of the highest location used by the object code.

There are two models for loader use; in one, the load-and-go model, the loader itself transfers control to the loaded routine immediately as it finishes loading, and then returns to the caller only when the loaded routine returns. The alternative is for the loader to load the program and then return to its caller; in that case, it must return the starting address of the loaded code so that the code that called the loader may then call the loaded program. The latter offers more flexibility, but the load-and-go model suffices for the most common usage pattern.

For the example system, the loader system service described below will be assumed. This does not use the load-and-go model, but it is easy to construct a load-and-go service using this service as a foundation.

loader(f,b,s,m)
load from open file variable f using relocation base b; return s, the starting address and m, the maximum address loaded. If there is no starting address, s=-1.

A loader system service.

The loader service described here relies on its caller to allocate memory for the loaded program, and it relies on its caller to handle any transfer of control to the loaded program. Typically, there will be some system wide convention about how the caller can transfer control to the program; a typical convention would require that the caller perform a procedure call to the starting address of the program, thus allowing the loaded program to return to the caller when it is done.

In systems where control is transferred to the loaded program by a goto instead of a call, the system must include a facility allowing the user to transfer control back to the caller when it is done. This is frequently done with a system service named end or exit; In systems that allocate activation records on a stack, this service also typically restores the stack to its state prior to entering the loaded program, and because of this, it is a useful way to terminate application programs when there is an exceptional condition.

Program termination by a call to a system service such as end or exit was especially important on systems which had very little memory. On such a system, it is common for the loader to load the new program directly into the memory which had been used by the caller, thus requiring the caller to be re-loaded when the loaded program finally terminates. The end or exit service could do this.

Small operating systems typically offered no storage management services at all. Such systems included the original MS-DOS in the early 1980s (the microprocessor era), or minicomputer operating systems of the 1960s, or mainframe operating systems of the 1950s. On such systems, user programs had to include their own storage management. A common storage management discipline on such a system establishes all of memory as a stack; whenever a program wants to load another program, it loads it immediately beyond itself in memory, thus effectively pushing one program on the stack. If procedure calls are done using a stack, this may require a second stack, as is shown in the map of the memory usage on such a small system given below.

 -----------------------------------------------------------------------
| code for |   command   |  user   |  user   |//////////////| procedure |
|  system  |  language   | program | program |//// free ////|  calling  |
| services | interpreter |    1    |    2    |//////////////|   stack   |
-----------------------------------------------------------------------
                             push (load) new ---->      <---- push activation
                             programs here                    records here

Map of the memory use in a typical small system.

The figure shows the state of the system while user program 2 is running, where user program 2 was loaded and then called by user program 1, and user program 1 was loaded and called by the command language interpreter. In this kind of simple environment, it is useful for a program to be able to find the highest address it occupies so that it can tell where memory is available to load any programs it needs. To simplify this, we will assume that the linker implicitly defines the relocatable symbol codetop as the address beyond the end of each loadable file.

On larger operating systems, services are usually provided for allocating and deallocating memory, and the loader frequently makes direct use of these services to obtain memory for the relocatable parts of loaded programs. The form that these services take is frequently strongly dependent on the structure of the system hardware; thus, these services are frequently quite different from the storage management services offered to user programs in high level languages (eg. Pascal new and dispose, C malloc and free, or C++ and Java object creation).

The use of loader system services by one user program which loads and calls another is very similar to the use of the same services when the main segment of a user program calls a procedure in one of its overlays. As a result, the explicit use of loader system services is sometimes described as a form of overlay management. An alternate view of this is that a user program which loads another and then calls it is making use of run-time linkage or dynamic binding, as opposed to pre-run-time linkage such as typically done with a linkage editor.

Communication Between Programs

When the command language interpreter loads a user program, or when one program loads another, a new problem arises: How can the newly loaded program be told why it was loaded and what it is to do? Some early systems did little to help solve this problem, so a program which was loaded was forced to open a communications channel with the user and ask why it was run and what it was to do. This made it very hard to write general utility programs that could be run interactively by a user one time, and run automatically by another program at a different time.

Since the 1960's, a common solution to this problem has been to introduce the concept of parameters to an executable program. This solution implicitly underlies the design of the Pascal language, where each program has a heading that lists, as parameters, the files 'input', 'output', and optionally others. Thus, it is reasonable to think of a Pascal compiler translating the heading of a program as illustrated below.

Original Pascal program heading:
program p( input, output, listing );
Equivalent C function heading:
#include <stdio.h>
void p( FILE *input, FILE *output, FILE *listing )

Program parameters.

This approach allows the user of a program to set up and open the files used by that program before running it, whether that user is another program or a person running the program via the command language interpreter.

Another approach to solving this problem is sometimes used on systems which maintain a table of opened files on behalf of each user. Under the classic OS operating system on the IBM 360/370/390 series of machines, where the opened file table has symbolic names for its slots, the slots named SYSIN and SYSPRINT are usually used for standard input and output by most programs, so a program which runs another program can first reset these files appropriately in order to change where input-output is directed when the new program is run. Unix uses a very similar scheme; in Unix and the many systems that have copied ideas from it, the integer unit numbers 0, 1 and 2 are used for standard input, standard output, and error messages, respectively. A program which wishes to run another program on particular input-output files can first close these units and then re-open them on the new set of files.

Although most Pascal systems only allow files as program parameters, there is nothing to prevent a language implementor from allowing arbitrary parameter types on a program. On systems where only files may be passed as program parameters, or where files are referenced through a system managed table of opened files, it is common to provide special mechanisms for communicating other kinds of information to programs. For example, some systems maintain a table of named variables, with special system services to set the value of a variable or to retrieve it.

The Unix model for communication with programs, a model that is fairly well incorporated into the standards for C and C++, includes two independent classes of program parameters. The first is a list of open files, indexed by file number, where file 0 is standard input, file 1 is standard output, and file 2 is standard error. The second is an array of textual parameters, operating as shown below:

An example C program
#include <stdio.h>
#include <math.h>
int main( int argc, char * argv[] )
{
    int i;
    printf( "argc = %d\n", argc );
    for (i = 0; i < argc; i++)
        printf( "argv[%d] = %s\n", i, argv[i] );
    return 0;
}
The command line used to execute this program
a.out runs the program
The output when the program is run
argc = 4
argv[0] = a.out
argv[1] = runs
argv[2] = the
argv[3] = program

Textual parameters to a C program

The example program above simply tests the passing of textual parameters to the main program by printing the parameter count and the parameters. The parameter count is passed as the first parameter, conventionally called argc, while the second parameter is an array of strings, conventionally called argv (the argument vector). The convention is that the first parameter, argv[0], is always the name of the program, and as a result, argc always seems to be one more than the number of parameters.

The implementation of this is straightforward. Prior to calling the function named main in a C program, the loader (or the program that called the loader) pushes each of the textual arguments on the stack, and after all of the arguments, it pushes the array of pointers to the arguments. Finally, after these, it pushes the count of arguments and a pointer to this array, as illustrated below:

                                                                   actual
                                                                 parameters
    | <-- stack top after return from program                    |-------|
 ________________________________________________________________________
    | a.out\0 | runs\0 | the \0 | program \0 | o | o | o | o | \0| 4 | o |
 ___|_^_______|_^______|_^______|_^__________|_|_|_|_|_|_|_|_|___|___|_|_|
      |         |        |        |____________|___|___|___|           |
      |         |        |_____________________|___|___|               |
      |         |______________________________|___|                   |
      |________________________________________|                       |
                                               ^                       |
                                               |_______________________|

The Unix/C model of how the call to a main program is implemented.

The example here also illustrates a feature of the C and Unix environments that many programmers find to be very obscure. The main program in C is not a procedure, but rather, it is an integer function. By convention, returning zero indicates a normal exit, while a nonzero value such as -1 indicates an error. C (or C++) programs may also terminate by calling exit(v) to return the value v without executing all the way to the end of the main program; this is like using the return command to escape prematurely from a function.

In a point-and-click windowing environment, programs also have parameters! In many ways, such environments are just another kind of command language. In such an environment, clicking on the icon for an object code file is a request to load and run the program in that file with no parameters, while dragging and dropping the icon for one file onto the icon for another is a request to load and run the program in the second file, passing the first file as a parameter. Typically, the part of the window manager that supports drag-and-drop execution passes the textual name of the file that was dragged and dropped as a parameter to the application.

An Example Command Language

A library of system services which allows any program to perform input-output operations and to load and run any other is a sufficient foundation for developing applications programs, but if that was the only componet of the operating system, we would have no way to start the computer running some application or to take control when that application terminates. In sum, we need a main program that can call the loader to load and run our application programs!

The primary function of this main program is to control the sequence of execution from one application to the next and to pass any parameters needed by the applications. To support this function, we invent command languages, and we refer to the main program as a command language interpreter. Sometimes, because the command language interpreter can be seen as a wrapper around applications, we refer to it as a shell. This terminology grew out of Unix usage. In the older world of punched cards, each deck of cards fed into a computer was frequently described as a job, and the term job control language or JCL is widely used to describe command languages that date back to the punched card era.

Textual command languages such as JCL for the IBM 360/370/390, the various Unix shell languages (the Bourne shell, the C-shell, Bash, Tcsh, etc), or the MS-DOS command language can be contrasted with the Window Icon Mouse Pointer or WIMP command languages supported by Microsoft Windows, Apple's MacOS and the X window manager under Unix. These windowing environments may not seem to support a language, but in fact, the replacement of text by sequences of mouse clicks does not change the status of the language as a language.

When we start a computer system, the bootstrap loader must load the command interpreter, the loader and the input-output library, and then it must start the command interpreter running. The command interpreter then begins reading commands in its command language and executing them. A simple command language interpreter for a trivial textual command language might have the form illustrated below:

program command_interpreter;

var in, load: filevariable;
    filename: string;
    start, stop: address;

begin
     open( in, 'keyboard' );
     while true do begin
          readline( in, filename, stringlength );
          open( load, s );
          loader( load, codetop, start, stop );
          { note that we're ignoring stop! }
          call( start );
     end;
end;

A simple command language interpreter.

The command language interpreter above reads commands from the keyboard, where each line of input is interpreted as the name of a file, or on a very simple system, the name of a device from which a program is to be loaded and then run. We assume a loader that takes, as parameters, the file to be loaded, the first address available for loading, and the variable to hold the starting address of the program, and then, we assume that the built-in function call() can be used to call the function that was just loaded, passing the starting address of that function.

Note that the interpreter given above handles a very simple command language. Each line of input from the keyboard holds the name of a file or device from which a program should be loaded and run. In fact, this is the core of all the Unix shell languages, but as with all practical command languages, the Unix shells allow much more.

A more useful command language should allow communication with the loaded programs using one of the communication techniques discussed in the previous section. Assuming that each program is written to accept exactly 3 files as program parameters, with no other program parameters, as as shown, the control language might have the form of a sequence of procedure calls, each taking 3 parameters, which are the names of files or, in a very crude system, the names of tape drives, where the special parameter "*" indicates that the called program is to use the same file or drive as was being used by the command language interpreter itself for the same purpose.

The figure below illustrates the use of this improved command language to assemble two files, link them, and run the result.

assemble( A, temp1, *)  -- 1, source on A, object to temp1
assemble( B, temp2, *)  -- 2, source on B, object to temp2
link( *, temp3, *)      -- 3, link to temp3
use "temp1"             -- 4, input to linker
use "temp2"             -- 5, input to linker
end                     -- 6, input to linker
temp3( *, *, *)         -- 7, run the linker's output

An illustration of the use of a command language.

In the above, the first two lines run the program found on the file or tape drive called assemble. Assuming that this is an assembler, it will take the source programs on files (or tape drives) A and B and produce object code on files (or tapes) temp1 and temp2.

The third line in Figure 8.11 runs a program from a file (or tape drive) called link. If this is the linker, we expect it to read a list of files to be linked from its input file; in this case, the input is from the same file being used for input to the command language interpreter, so it reads the lines that follow, lines 4, 5 and 6. The output of the linker is directed to temp3. The linker we are using in this example reads a list of linker commands its input file; in this case, two use commands indicating the names of files to be linked, and an end command indicating that there are no more files to be linked.

The final line in Figure 8.11 goes to the command interpreter, telling it to run the program that the linker wrote to temp3. This is run with all input and output directed to the same files used by the command language interpreter.

Looking over Figure 8.11, it is easy to see that we never need more than 3 tape transports, but if we have no concept of files more complex than "the cassette tape loaded on some transport", we'd have to stop and change tapes at almost every step shown in the figure. On the other hand, if we have 5 tape transports named assemble, link, temp1, temp2, and temp3, we would be able to do very complex program development. This is why those old computer centers that used half-inch magnetic tape for everything frequently had a long wall of tape transports.

While a file system that allows multiple named files to be stored on one device makes everything more convenient, the file system itself is not usually part of the command language, but rather, is part of the underlying library of input-output services, available for use equally by the user program and the command language interpreter. Even if we ignore this, the command language interpreter itself is usually far more complex than that suggested above. The Unix shell languages are quite typical; while they differ in many details, all of the common Unix shells support supersets of something like the syntax given below:

<command> ::= <filename> { <parameter> } [ < <infile> ] [ > <outfile> ]
The full syntax of a Unix shell command is complex, so we will break it down in the following sections.

<command> ::= <filename>
Normally, if you type a file name in on a line by itself, the shell will simply execute the code in that file, letting that program read input from the same file the shell was reading from and letting the program write output to the same file the shell was writing its output to.

<command> ::= <filename> <parameter1> <parameter2>
If additional lexemes appear following the file name (identifiers, quoted character strings), they are passed as textual parameters to the program being executed.

<command> ::= <filename> < <infile>
If the command includes a < symbol, the text following this is interpreted as a file name, and that file is opened as the input file for the program being loaded and run.

<command> ::= <filename> > <infile>
If the command includes a > symbol, the text following this is interpreted as a file name, and that file is opened as the output file for the program being loaded and run.

<command> ::= <command> ; <command>
A sequence of commands may be given on one line, separated by semicolons. When this is done, they are executed left to right, in sequence.

<command> ::= <command> && <command>
When a double ampersand separates the commands on a line, the program on the left is loaded and run first, and only if its return value is zero is the program on the right run. Recall that, by Unix convention, programs return zero to indicate that execution was successful. they return nonzero to indicate that an error occurred.

<command> ::= <command> || <command>
When a double vertical bar separates the commands on a line, the program on the left is loaded and run first, and only if its return value is not zero is the program on the right run. Recall that, by Unix convention, programs return nonzero values to indicate errors.

A grammar for a Unix-like shell command language

It is worth noting that the .BAT file command language of Microsoft's DOS and Windows operating systems borrows heavily from the language of the Unix shell. The biggest difference naive users will notice is that command-line options to Unix programs are usually given using parameters that start with - (hyphen) while such options in the Microsoft world usually begin with \ (backslash). This difference dates back to the command language interpreter RT-11, the operating system on which the very first version of DOS was based, before Microsoft bought the system, and before they began to borrow from Unix.

Both the Unix and Microsoft command languages allow one command language file to call on another. In Unix, execv, the Unix load-and-go system service does this using a very general mechanism. Whenever an object file is loaded, the loader always inspects the first two bytes of that file. If these bytes are a "magic number" indicating that the file contains executable machine code, the loader operates normally, loading that file and then calling the main program of the file that was loaded. If, on the other hand, the file begins #sh or #csh (or, for that matter, #name, where name is the name of any particular object file, the loader will load and execute that object file as an interpreter, applying the interpreter to the file that referenced it.

In effect, Unix files starting with #sh or #csh are command language files that are executed by the indicated shell. In Unix, such files are referred to as shell scripts; the corresponding Microsoft terminology is a .BAT file because Microsoft's command shell detects the file type by the extension on the file name instead of by the "magic number" at the head of the file. In many ways, shell scripts or .BAT files serve as shell macros, and most of the concepts of macro expansion apply; for example, in a Unix shell script, the names $0, $1, $2 and so o refer to the textual arguments to the shell script, just as if they were macro parameters. Furthermore, because all common shells contain conditional mechanisms (for example, the && and || mechanisms of the Unix shells), we typically have the complete flexibility of conditional and macro assembly in our command shells!

Before the command language interpreter acts on a line, it performs some simple macro substitution. All common Unix shells use the following notation for this substitution:

$<digit>
substitute the indicated parameter; script one two three will, for example, replace $1 with one, $2 with two and $3 with three, assuming that script is the name of a shell script.

In sum, all of the Unix shells incorporate conditional and macro processors, and in fact, all of the Unix shells are sufficiently general that the shell languages are, in fact, fully sufficient to be used to write any computer program without resorting to executing any machine code other than the command language interpreter. Unfortunately, the different shells are incompatable with each other for all but the most elementary purposes, so it is necessary to ask a Unix shell programmer whether he knows sh (the original Unix shell, known as the Bourne shell, after its author), csh (the C shell), bash (the "Bourne again" shell) or some other.

The reason that there are so many Unix shells is that there is nothing special about the Unix shell. Several are distributed with each Unix system, but programmers are entirely free to write their own if they don't like the shells that come with Unix. This is quite different from, for example, the old IBM JCL command language or, for that matter, Microsoft's .BAT command interpreter or Microsoft's window manager; in these cases, the division between command language interpreter and the remainder of the operating system has been concealed by the system's developer. In these proprietary systems, it is possible that these command language interpreters are actually well engineered components, easily separated from the underlying system, but the vendor claims always emphasize that they are tightly integrated into the system, which is to say, it is quite possible that they are poorly engineered and not an easily separable components.

The classic job control language of the classic OS operating system on the IBM 360/370/390 series of computers is worth illustrating, albeit breifly. A JCL program consists of a series of job steps, where each job step may consists of several lines describing the loading and execution of one program. A job step consists of a number of DD (data definition) lines which describe the files which a program is to use, followed by an EXEC line which specifies the program which is to run using those files. The reason that IBM JCL takes so much more text than the Unix shell language is that the file descriptions needed to open a file under the OS operating system are very complex, including not only the file name, but the block size to be used for reading or writingwith the file, the logical record size of the file, and many other parameters.

Terminology

The reader should be familiar with the following terms after reading this section:

run-time services               storage management
command languages               dynamic linkage
supervisor call instructions    run-time binding
opened file descriptors         program parameters
file variables                  command language procedures
input-output primitives         Unix shell
file control blocks             IBM job control language

In addition, the reader should be familiar with the following system services of the example operating system:

open                            writeblock
rewind                          readline
read                            writeline
write                           loader
readblock                       codetop

Exercises

  1. Using only the basic input-output services suggested in Figure 8.3, propose implementations of:

    a) readblock, as defined in Figure 8.4.

    b) writeblock, as defined in Figure 8.4.

    c) readline, as defined in Figure 8.4.

    d) writeline, as defined in Figure 8.4.

    You should probably write these in an informal pseudocode and not in a formal high level language.

  2. Using only character-sequential input primitives, that is, primitives that read one character at a time from a file, write readline, a utility routine that reads and returns one line of text as some kind of string variable. The particular primitives used for character-sequential input and the nature of the variable used to return a string will depend on the language you elect to use.

  3. Propose implementations of the the character sequential read routine in figure 8.3 in terms of the block sequential readblock routine in figure 8.4. To do this, you will have to assume that each file variable has several components, for example, the block size to use for this file, the current position in the block, and perhaps the current block itself. Present your answer as pseudocode.

  4. In the chapter on linkers, it was mentioned that calls from the main program to procedures in an overlay were replaced with calls to a load-on-call stub which loads that overlay and then passes control to the desired procedure. Consider a parameterless procedure p which has been link edited into an overlay stored in file pfile. Write code for a load-on-call stub for p using the loader service suggested in Figure 8.5. The code shown in Figure 8.10 may provide a useful illustration of how to do some of the operations needed for this.

  5. On a system with loader services such as are suggested in Figure 8.5, where memory is organized as suggested in Figure 8.6, how would you detect that the system is out of memory, and when would you make checks for this situation? Assume that the stack has one entry pushed on it each time a procedure or function is called, and that this entry holds all local variables and any other memory needed by that procedure.

  6. In some systems, user programs can call the command language interpreter as a function, passing it an open file from which commands are to be interpreted, and user programs can call the a command-line interpreter, which takes just one command line as a parameter, plus the a list of current parameters that may need substitution, and interprets just that line..

    a) Redraw Figure 8.2 to take into account both of these. You should show the fact that the command language interpreter and the user may both call the command line interpreter, the fact that the command line interpreter is the one that calls user programs, and the fact that the user may also call the command language interpreter. Don't expect a pretty result!

    b) Write code, in the style of Figure 8.10 (but in the language of your choice) to implement the command line interpreter.

    c) Write code, in the style of Figure 8.10 and using your answer to part b to implement the command language interpreter library routine.

    d) Write code, in the style of Figure 8.10 and using your answer to parts b and c to implement an appropriate main program so that, when the system first begins operation, the command language interpreter begins reading commands from the keyboard.

References

The subjects discussed in this chapter are covered to a remarkably uneven extent in the literature. Many authors seem to consider system command languages to vary so extremely that there is little that unifies the command languages of different systems, while others consider the subject to be so elementary that it does not require discussion. The discussion of command languages in Section 4.4 of

The Logical Design of Operating Systems by A. C. Shaw (Prentice Hall, 1974).

may be helpful. Section 7.4 of

Operating System Elements, A User Perspective by P. Calingaert (Prentice Hall, 1982).

is also a reasonable source.

For a discussion of the classical IBM 360/370/390 job control language, see

Operating Systems by H. Lorin and H. M. Deitel (Addison Wesley, 1981).

This discussion starts in Section 2.3.2, and continues in Section 6.4.1. Chapter 7 contains a discussion of system services, although the term is used slightly differently than it is here; this chapter includes a discussion of the command language interpreter.

For information on Unix, see

Understanding Unix, a Conceptual Guide by J. R. Groff and P. N. Weinberg (Que, 1983)

Chapter 5, contains an extensive discussion of the Unix shell. The official description of the Unix shell is included in section sh(1) of the

Unix Programmers' Manual, Vol. I (Holt, Rinehart and Winston, 1983).

Sections open(2), read(2), write(2), and lseek(2) provided much of the inspiration for the basic input-output services discussed in this chapter. Section exec(2) documents the way in which the Unix loader is called; this was not used as a pattern for the loader service described here, but is an interesting contrast.

Any Unix system should support the man command, and should have, on line, a complete copy of the Unix Programmers' Manual, updated appropriately for that system. Any command that is documented as command(x) can be looked up using the command man x command.

The classic introduction to the Unix system and a basic introduction to the system services and shell is included in the paper

"The Unix Time-Sharing System" by D. M. Ritchie and K. Thompson in Communications of the ACM 17, 7 (July, 1974) 365-375.

For a look at the kind of effort required to retrofit old operating systems with small memory models to support a reasonably modern view of the kind of dynamic linking suggested by the example in Figure 8.10, see

"Programs as Higher Level Subroutines" by D. Jones, et al, in Software - Practice and Experience 9, 2 (Feb. 1979) 149-155.

This paper also includes a small example showing the different programs in a real user's environment with an indication of which programs dynamically load and call which others.

Desktops

The Xerox corporation undertook an interesting venture in the 1970's, investigating the automated office of the future. They decided to abandon all financial good sense and imagine an era when computers were inexpensive enough that each office worker could have their own computer on their desk. Cost was no object, so they imagined each office worker having a machine with a full 64K bytes of main memory, a disk drive, and a graphics display screen, and they imagined all these machines networked, with a laser printer on the net.

The prototype, called the Alto, after the Xerox Palo Alto Research Center, was a very expensive machine. They added a mouse to it, the idea came from Stanford Research Institute, and they developed a new network protocol for the network, called Ethernet. The keyboard, display screen and mouse sat on the desktop, while the electronics filled a small 19-inch wide relay rack next to the desk.

The next question is, what to do with this hardware. Several tens of these machines were distributed to workers at PARC and eventually also at Xerox Webster Research Labs in New York. Several different uses were found for the machine. One branch of development pursued the Smalltalk language, while another looked at how to do document formatting on these machines.

One result of this work was the idea of the WIMP model of user interface, that is, the Window Mouse Icon Pointer model. This model now dominates all desktop computers, and it has its roots in earlier graphics systems, but it reached its first maturity at Xerox PARC.

The Basic Idea

As anyone who has used a Mac or Windows PC knows, the basic idea of the WIMP user interface is that the screen is a desktop, with icons on the screen representing objects you are able to use or manipulate. Clicking on an object on this desktop typically opens a window allowing you to manipulate the object.

The application launched depends on the type of the object. If you click on a word-processing document, you laungh the word processor. If you click on a directory object, you launch the directory manager. If you click on a JPG object, you launch an image viewer, and so on.

This basic WIMP model suggests something of an object-oriented world view, where each file is an object, in the object-oriented programming sense of the word. All file objects are therefore required to have a "click on me" method that opens the window to manipulate that object.

This viewpoint has its limits, but it immediately asks: What about other methods of the object? Object-oriented programming where each class has just one method is a very limited view. There are several ways WIMP user interfaces have dealt with this:

More mouse buttons: Left click and right click can call two different methods, or single click and double click. So long as there are only two or three things anyone might want to do with an object, this works.

Method select menus: Clicking on an icon causes a popup or pulldown menu to appear listing the available operations on the object.

Combinations of the above: Clicking the left button invokes the most common method, while clicking the right button opens the menu of other methods.

Drag and drop: Instead of clicking on an icon, drag it to another icon and drop it there. This launches a method of the destination icon passing the dragged object to it as a parameter.

Attributes

In a conventional file system, each file has two attributes: A name and a value, where the value is the entire contents of the file.

In systems like Linux, file names are entirely uninterpreted by the system, but users quickly adopted the convention of putting suffixes on file names to indicate their use.

Additional headings emerged on other systems, where suffixes were mandatory:

On some systems, some of these suffixes have rigidly determined meanings, while on other systems such as Linux, they remain advisory.

This system of adding attributes to files as extensions of the file name is very limited. In the context of the WIMP world view, it is entirely inadequate.

WIMP Attributes

In the WIMP world, each file needs the following attributes:

This list led Apple and some later WIMP GUI developers to decide that each file in the MacOS file system should have two parts, a resource fork and a data fork. The resource fork of a file is for listing all these attributes, while the data fork is the actual content of the file. In theory, the resource fork should be short, but it can be significant.

There is another issue. Where on the desktop should each icon be displayed. It is fair to ask, is this an attribute of the file, or is it an attribute of the desktop. Does moving a file change it, or does it merely change a record of the desktop. The usual conclusion is that the location belongs to the desktop, not to the file.

One option is to augment every directory entry with coordinate information, so that when that directory is viewed, the objects in that directory are displayed with coordinates taken from the directory. In this case, the desktop itself is naturally a kind of directory.

An Example Desktop Manager

Given directory entries containing coordinates, and given that each file has a resource fork, we can construct the core of a desktop manager as follows:

        /* first plot, or replot the screen */
        for each directory entry e {
                file f = e.file
                at e.coordinates
                display f.resources.icon
        }
        /* then process mouse clicks */
        loop {
                await mouse click c
                for each directory entry e {
                        if c.coordinates is near enough to e.coordinates {
                                file f = e.file
                                launch application f.resources.click
                                passing f to it as a parameter
                        }
                }
        }