Section 7: Shell

Section 7 video

Open up a new terminal window on your computer. Congratulations, you’ve opened up a UNIX Shell (unless you opened Command Prompt)! So far, you’ve used this wonderful utility to run around your filesystem, possibly open some code, build your pset, and/or play around with Git. Isn’t it magical? Its builders must’ve been geniuses.

Fortunately, you too are a genius, because you will be implementing a (slightly simpler) shell for pset 5. That is, you’ll learn The Inner Life of a Shell. The UNIX shell is an interesting work of art, but deep down, it just parses the input you type, forks subprocesses to run the resulting commands, waits for some of those processes to finish, and subsequently execute the next commands. In pset 5, you will be given the rudimentary tools to parse the command line input and some shell code to get you started. You will:

1. Use fork() to create subprocesses, use exec() to load the program’s code, and examine the output of exit() to determine the “success” of the execution.
2. Interpret command line syntax to emulate more complex behavior, e.g. a && b will only run b if a is successful.
3. Use pipes to direct input to and output from a program.

This section helps you get familiar with shells by writing short shell programs. It also introduces you to BNF grammars, a notation technique used to precisely describe languages, such as valid command lines; and describes some implementation choices your shell will face. The shell exercises are in the s07 directory of the cs61-sections repository. Refer to the shell descriptions at the bottom of these section notes to complete these exercises.

Warmup exercise

Exercise A: Use only shell commands to print the contents of file1.txt and file2.txt into the console, in that order.

cat file1.txt file2.txt

Process I/O and redirections

As you saw in pset 4, I/O is very important, and UNIX implements I/O using file descriptors. By convention, file descriptor 0 is used for programs’ standard input (STDIN or std::cin), 1 for standard output (STDOUT or std::cout), and 2 for standard error (STDERR or std::cerr). Of these, 0 is often open only for reading, while 1 and 2 are often open only for writing. (Although when you run a program at a terminal prompt, all three file descriptors often point at the same stream file, the “keyboard/console”.)

How, then, are the standard input, output, and error created, handled, and used? Remember that they’re simply file descriptors, so the strace output you looked at in pset 4, including the read and write syscalls, can be used for this purpose.

The standard input, output, and error file descriptors are typically set up for a process before the process begins. That is, these file descriptors form part of the process’s initial environment. Once a process starts running, its environment is primarily under its control—for instance, a process can close its own standard input if it wants to. But it’s possible to set up a process’s initial environment before the process begins.

Shell redirections change a process’s initial environment by associating its standard input, output, and/or error with files, rather than the console. For example, these two commands execute identical write system calls:

echo hello kitty
echo hello kitty > cs61.txt

But in the first case, hello kitty is printed to the terminal, and in the second, hello kitty is saved to a file named cs61.txt in the current directory. (You can verify this with ls and less cs61.txt.)

Exercise: Use strace to verify that the write system calls are in fact identical.

Example strace command lines:

strace -o s1.out echo hello kitty
strace -o s2.out echo hello kitty > cs61.txt

Both commands execute write(1, "hello kitty\n", 12), and neither output mentions the file cs61.txt by name.

Exercise B: What effects do these two commands have? Which file descriptors are read and written in both cases?

echo hello kitty > cs61.txt
cat < cs61.txt

The first line writes hello kitty to cs61.txt. The second line reads cs61.txt and writes its contents to the console.

Exercise: Which file descriptors are read and written in both cases?

echo reads nothing and writes standard output, while cat reads standard input and writes standard output. (If you verify this with strace, you’ll see that both programs read other file descriptors corresponding to the process initialization procedure, such as /etc/ld.so.cache and /usr/lib/locale/locale-archive.)

Exercise: Which file descriptor does the < operator redirect?

Standard input.

Exercise: Will the following commands produce different output than those in Exercise B? Will they access different file descriptors?

echo hello kitty > cs61.txt
cat cs61.txt

They will produce the same output, but in the second example, cat will explicitly open the cs61.txt file. It reads file descriptor 3, which corresponds to cs61.txt, and does not read standard input.

Kinds of redirection

< redirects standard input and > redirects standard output.

> will truncate the file if it already exists (this means it initially sets the file to zero length). >> is like >, but will append to the file if it already exists.

2> sometxt means “redirect file descriptor 2 to sometxt for writing.” Note that there is no space between 2 and >.

2>&1 means “make file descriptor 2 point to the same file structure as file descriptor 1.” This causes writes to standard error to be redirected to standard output. Again, note that there is no space between > and &.

The purpose of 2>&1

The 2>&1 idiom can be very useful for commands that generate a ton of errors. For example, consider manyerrors.sh, which generates output for both standard output and standard error. Then compare how the following commands behave (use Control-C to quit if things seem out of hand).

sh manyerrors.sh
sh manyerrors.sh | less
sh manyerrors.sh 2>&1 | less

Exercise: Repeat Exercise A, but store the result in a file called cs61.txt.

cat file1.txt file2.txt > cs61.txt

Exercise: Do it again, but with a different sequence of commands.

cat file1.txt > cs61.txt
cat file2.txt >> cs61.txt

There’s an infinite number of possibilities.

Exercise C: Write a sequence of commands that prints the names of the two files in the current directory that come last in alphabetical order. For example, in a directory with files named a through z, you should print

z
y

Use redirections, not use pipes (pipes show up in the next section).

ls > a1.txt
sort -r < a1.txt > a2.txt
head -n 2 < a2.txt

BNF grammars

The input language for sh61 command lines is described in terms of a BNF grammar, where BNF stands for Backus–Naur Form, or Backus Normal Form. BNF is a declarative notation for describing a language, where a language is a set of strings. (Specifically, BNF can describe any context-free language.) BNF notation consists of three pieces:

• Terminals, such as "x", are strings of characters that must exactly match characters in the input.
• Nonterminals (or symbols for short), such as lettera, represent sets of strings. One of the nonterminals is called the root or start symbol of the grammar. By convention, the root is the first nonterminal mentioned in the grammar.
• Rules, such as lettera ::= "a" or word ::= letter word, define how nonterminals and strings relate.

A string is in the language if it can be obtained by following the rules of the grammar starting from a single instance of the root symbol.

Here’s an example grammar that can recognize exactly two sentences, namely "cs61 is awesome" and "cs61 is terrible":

cs61 ::= "cs61 is " emotionword
emotionword ::= "awesome" | "terrible"

It’s useful to be able to read BNF grammars because they’re ubiquitous in computer science and programming. Many specification documents use BNF to define languages, whether programming languages or even languages of network packet formats.

We’ll describe the features of BNF grammars using simple examples. Peek at some answers and then try to answer the questions on your own.

Exercise: Define a grammar for the empty language, which is a language containing no strings. (There is no valid sentence in the empty language.)

shutup ::=

This grammar has one nonterminal, the root symbol shutup. The ::= notation has nothing on the right, indicating that no string will match shutup.

Exercise: Define a grammar for the children language (because children should be “not heard”). The empty string is the only valid sentence in this language.

children ::= ""

Note the difference between children and shutup. The shutup language contains no sentences: no string is valid in this language, not even the empty string. The children language contains one sentence: the empty string "" is valid.

Exercise: Define a grammar for the letter language. A letter is a lower-case Latin letter between a and z.

letter ::= "a" | "b" | "c" | "d" | ... | "z"

The | symbol indicates alternate choices for the rule’s definition. It’s actually shorthand for multiple rules for the same nonterminal:

letter ::= "a"
letter ::= "b"
letter ::= "c"
letter ::= "d"
...
letter ::= "z"

Exercise: Define a grammar for the word language. A word is a sequence of one or more letters. You may refer to the letter nonterminal defined above.

word ::= letter | word letter

This grammar features a recursive rule! Why is "butt" a valid sentence in this language? Well:

• "b" is a word (a sentence in the word language) because it is a letter. (This uses the first alternative, word ::= letter.)
• "bu" is a word because "b" is a word (see above) and "u" is a letter. (This uses this second alternative, word ::= word letter.)
• "but" is a word because "bu" is a word and "t" is a letter.
• "butt" is a word because "but" is a word and "t" is a letter.

Exercise: Define two different grammars for the word language.

word1 ::= letter | word1 letter

word2 ::= letter | letter word2

word3 ::= letter | word3 word3

Each of these grammars recognizes the same language: every string that matches the word1 nonterminal matches word2 and word3, and every string that doesn’t match word1 doesn’t match word2 or word3 either.

It is possible to prove that these simple grammars recognize the same language, but in general, testing whether two context-free grammars recognize the same language is undecidable! There is no algorithm that can reliably report whether two grammars are effectively the same. If this blows your mind (and it should), take CS121.

Exercise: Define a grammar for the parenthesis language, where all sentences in the parenthesis language consist of balanced pairs of left and right parentheses. Some examples:

An important question is, is the empty string a valid sentence in this language? Let’s say yes. Then this works:

parens ::= "(" parens ")"
        |  parens parens
        |  ""

Note that the following subset grammar accepts no finite strings:

parens2 ::= "(" parens2 ")"

This is because this recursion has no base case. (You could argue that the infinite string consisting of an infinite number of (s, followed by an infinite number of )s, would match the grammar, but also you could argue that it would not, because infinity is weird.)

The balanced parenthesis language is context-free, but not regular. In practical terms, this means that no regular expression can recognize the language. Regular expressions are too limited to remember a nesting depth.

The shell grammar

This is the BNF grammar for sh61, as found in problem set 5. (Note that this grammar doesn’t define words, and doesn’t define where whitespace is required. That kind of looseness is typical in systems grammars; in your case helpers.cc already implements the necessary rules.)

commandline ::= list
          |  list ";"
          |  list "&"

list     ::=  conditional
          |   list ";" conditional
          |   list "&" conditional

conditional ::=  pipeline
          |   conditional "&&" pipeline
          |   conditional "||" pipeline

pipeline ::=  command
          |   pipeline "|" command

command  ::=  word
          |   redirection
          |   command word
          |   command redirection

redirection  ::=  redirectionop filename
redirectionop  ::=  "<"  |  ">"  |  "2>"

The recursive definitions allow for lists or trees of terms to be chained together. Taking list as an example:

list     ::=  conditional
          |   list ";" conditional
          |   list "&" conditional

This reads “a list is a conditional, or a list followed by a semicolon and then a conditional, or a list followed by an ampersand and then a conditional.” But this means that the list is just a bunch of conditionals, linked by semicolons or ampersands! Notice that the other recursive definitions in sh61’s grammar also follow this pattern. In other words:

• A list is a series of conditionals, concatenated by ; or &.
• A conditional is a series of pipelines, concatenated by && or ||.
• A pipeline is a series of commands, concatenated by |.
• A redirection is one of <, >, or 2>, followed by a filename.

We’ve explicitly written out the definition of command, but it would be common to see this written in shorthand such as

command ::= [word or redirection]...

So a command is a series of words representing the program name and its arguments, interspersed with redirection commands.

Command line representation

The shell grammar makes the underlying hierarchical structure of command lines explicit and clear. The overall structure of a line, as described by the grammar, is:

• A list is composed of conditionals joined by ; or & (and the last command in the list might or might not end with &).
• A conditional is composed of pipelines joined by && or ||.
• A pipeline is composed of commands joined by |.
• A command is composed of words and redirections.

So lists are comprised of conditionals, which are comprised of pipelines, which are comprised of commands. But must this structure be reflected in your implementation?

There are two common ways to represent our parsed command line in a data structure appropriate for our shell, a tree representation and a list representation. Students often are biased toward the tree representation, which precisely represents the structure of the grammar, but the list representation can be easier to handle! The tradeoff is simplicity vs. execution time: the list representation requires more work to answer some questions about commands, but command lines are small enough in practice that the extra work doesn’t matter.

Tree representation

The following tree-formatted data structure precisely represents this grammar structure.

• A command contains its executable, arguments, and any redirections.
• A pipeline is a linked list of commands, all of which are joined by |.
• A conditional is a linked list of pipelines. But since adjacent conditionals can be connected by either && or ||, we need to store whether the link is && or ||.
• A list is a linked list of conditionals, each flagged as foreground (i.e., joined by ;) or background (i.e., joined by &). Note that while the conditional link type doesn’t matter for the last pipeline in a conditional, the background flag does matter for the last conditional in a list, since the last conditional in a list might be run in the foreground or background.

For instance, consider this tree structure for a command line (the words and redirections that are there, but not being shown for the sake of simplifying the image somewhat):

Exercise: Assuming that a, b, c, d, e, and f are distinct commands, what could be a command line that would produce this tree structure?

a & b | c && d ; e | f &

Exercise: Sketch a set of C++ structures corresponding to this design.

Here’s one:

struct command {
    std::vector<std::string> args;
    command* command_sibling = nullptr;
};
struct pipeline {
    command* command_child = nullptr;
    pipeline* pipeline_sibling = nullptr;
    bool is_or = false;
};
struct conditional {
    pipeline* pipeline_child = nullptr;
    conditional* conditional_sibling = nullptr;
    bool is_background = false;
};

There are many other solutions. Logically, we need a struct for conditional chains that indicates whether the chain should be run in the foreground or background; a struct for pipelines; and a struct for commands. Each struct needs to hold the necessary pointers to form a linked list of siblings. Furthermore, conditionals and pipleines need a pointer to the first item of their sublists.

Exercise: Given a C++ structure corresponding to a conditional chain, explain how to tell whether that chain should be executed in the foreground or the background.

For our solution, that’s as simple as c->is_background.

Exercise: Given a C++ structure corresponding to a command, how can one determine whether the command is on the left-hand side of a pipe?

For our solution, a command c is on the left-hand side of a pipe iff c->command_sibling != nullptr.

Exercise (left to the reader): Given a C++ structure corresponding to a command, how can one determine whether the command is on the right-hand side of a pipe?

Linked list representation

Alternatively, we can create a single linked list of all of the commands. In this case, we also store the connecting operator (one of & ; | && or ||). For our example command line above, the flat linked list structure might look something like:

Again, this is the structure we recommend (we don’t require it). Traversing this structure is slightly more time-consuming than in the tree representation, but the structure is much easier to build, and the additional CPU time spent traversing it is in the noise given how short command lines typically are.

Exercise: Write a set of C++ structures corresponding to this design.

Here’s an example:

struct command {
    std::vector<std::string> args;
    command* next = nullptr;
    int link = TYPE_SEQUENCE;  // Operator following this command.
                    // Always TYPE_SEQUENCE or TYPE_BACKGROUND for last in list.
};

Much simpler!

Another good one, with fewer pointers and thus fewer opportunities for memory mistakes, but harder to traverse (you need C++ iterators):

struct command {
    std::vector<std::string> args;
    int op;         // as above
};
using command_list = std::list<command>;

Exercise: Given a C++ structure corresponding to a conditional chain, explain how to tell whether that chain should be executed in the foreground or the background.

bool chain_in_background(command* c) {
    while (c->op != TYPE_SEQUENCE && c->op != TYPE_BACKGROUND) {
        c = c->next;
    }
    return c->op == TYPE_BACKGROUND;
}

Things are slightly more complicated with a flat linked list. We are still executing commands sequentially, but some subsequences of commands may need to be executed in the foreground or the background. During parsing, we can skip ahead in the command line to find the end of our current list (i.e., our current chain of conditionals).

Exercise (left to the reader): Given a C++ structure corresponding to a command, how can one determine whether the command is on the left-hand side of a pipe?

Exercise (left to the reader): Given a C++ structure corresponding to a command, how can one determine whether the command is on the right-hand side of a pipe?

Exercise (left to the reader): Sketch out code for parsing a command line into these C structures.

Pipes

Having covered grammars and the different representation choices available for command lines, we return to examples of shell programlets.

Exercise: The following command line contains one pipe. What does it do?

ls | head -n 2

It prints the first two items listed in the output of ls.

Exercise: Repeat Exercise C using pipes.

ls | sort -r | head -n 2

Much nicer than redirecting to and from files, and it leaves less garbage around.

Pipes take information from one process and spit it into another. Pipes also have another distinct advantage: in command1 | command2, command2 can start working on the output of command1 before command1 has fully completed!

Question: How many pipes can be chained together in one line? Can you find a limit?

Technically, there’s no fixed limit, but in practice operating systems impose limits on the total number of file descriptors allowed, shells impose limits on the length of command lines, and there are RAM and CPU limits.

A sequence of one or more processes, connected by pipes, is called a pipeline. (A single process is a trivial pipeline.)

Use only shell commands to complete the following tasks. Refer to the the shell descriptions to help you find and use the proper shell utilities.

Exercise: Count the number of lines in the file words (and print the count).

wc -l words

Exercise: Print every unique line in the file words exactly once.

sort -u words

Exercise: Count the number of unique lines in the file words (and print the count).

sort -u words | wc -l

Exercise: Write a command that could help you discover whether a shell really executes the two sides of a pipeline in parallel. Describe the result if (1) the shell executed the left side to completion first (and buffered the output for the right side to read), (2) the shell executed the sides in parallel.

Any number of solutions, but sleep 10 | echo foo is a classic one. If the pipeline is executed left-to-right with intermediate buffering, we’d see nothing printed for 10 seconds while the sleep counted down, then we might see foo printed afterward. If the pipeline is indeed executed in parallel, then we’d see foo printed immediately instead.

Putting commands together

Pipes aren’t the only way to put commands together! Shells also allow us to run commands in sequences called command lists. And some of those ways let us detect and respond to failures.

First, the ; operator says “run this, then run that.” The semicolon waits for the left-hand command to complete. Then it executes the right-hand command.

Exercise: Write a single shell command list that repeats Exercise A, but runs two separate commands in a single command list.

cat file1.txt > cs61.txt ; cat file2.txt >> cs61.txt

Now, shell commands, and processes in general, can either succeed or fail. A process indicates its status when it exits by passing an integer (between 0 and 255) to the exit() library function. By convention, the zero status indicates success, and all non-zero statuses indicate failure. That is, successful processes are all alike; every failing process fails in its own way.

The exit library function is a wrapper around the _exit system call. Most programs will call exit, which takes care of important cleanup tasks such as flushing standard I/O buffers. In your shell, however, you will call _exit.

To test different statuses, we often use the true and false programs. true just exits with successful status: exit(0). false just exits with the unsuccessful status 1: exit(1). If you’re feeling verbose, you can say exit(EXIT_SUCCESS) and exit(EXIT_FAILURE) instead.

Exercise: Write C++ code that compiles to a program equivalent to true.

#include <cstdlib>
int main() {
    exit(0);
}

Exercise: Write C++ code that compiles to a program equivalent to false, but don’t call exit explicitly.

int main() {
    return 1;
}

In well-written programs, errors that cause the program to exit should cause a failing exit status. For instance, cat will fail if it is passed a nonexistent file.

Exit status is commonly checked by the shell && and || operators. These are like ;—they execute the left-hand command first, then turn to the right-hand command—but unlike ;, they check the status of the left-hand command, and only run the right-hand command if the left-hand command has an expected status.

Exercise: Use true, false, and echo to figure out what statuses && and || expect.

The && operator executes the right-hand command if the left-hand command succeeds. The || operator executes the right-hand command if the left-hand command fails. We might figure that out with commands like this:

true && echo left side succeeded 1
false && echo left side failed 2
true || echo left side succeeded 3
false || echo left side failed 4

That will print:

left side succeeded 1
left side failed 4

In command lists with multiple conditionals, the conditionals run left to right.

Exercise: What status does false && echo foo return? Use more conditionals to figure it out.

It returns the status of false, which is 1. false && echo foo || echo bar and false && echo foo && echo quux would help you figure out that false && echo foo has a failing exit status; you’d have to use other features, such as $?, to figure out the exact status.

Exercise: Run and print the numerical exit status of true to the shell. (If you’re working through on your own, read manual pages here, or look below at our documentation.)

true; echo $?

More exploration

In lecture, we discussed some of the shell utilities—if you’d like to discover more and have more practice with them, here are some exercises to help you along your way.

Use only shell commands to complete the following tasks.

Exercise: Run and print the exit status of false to the shell.

false; echo $?

Exercise: Print the exit status of curl http://ipinfo.io/ip to the shell.

curl http://ipinfo.io/ip; echo $?

Exercise: curl a URL and print Success if the download succeeds, or Failure if the download fails.

curl lcdf.org && echo "Success" || echo "Failure"

Exercise: Do it again, but store the downloaded result in a file called ip.

curl lcdf.org > ip && echo "Success" || echo "Failure"

Documentation and References

Feel free to refer to these during section and as you work on pset 5.

Useful shell utilities

Here are some commonly-installed, commonly-used programs that you can call directly from the shell. Documentation for these programs can be accessed via the man page, e.g. man cat, or often also through a help switch, e.g. cat --help.

sh61 shell subset

For pset 5, you will be expected to implement a subset of common UNIX shell features. Try a few of them now, and start thinking about how you might consider implementing them!

Non-sh61 shell features

Here are some commonly-used features of a more fully-implemented shell (like the one you generally use!), but won’t be part of the sh61 assignment. Take a look, some of them are incredibly powerful!