\documentclass[structure=hierarchic]{cweb}
\usepackage{amsmath,amsthm,amssymb,stmaryrd,stmaryd}
\usepackage{xcolor,tcolorbox,mdframed,epigraph,soul}
\usepackage{array,tabularx,minted,graphicx,fancyhdr}
\usepackage{tikz,simplebnf,oz}
\usepackage{filecontents}
\usepackage[backend=biber,style=authoryear]{biblatex}
\usepackage{makeidx,authblk,hyperref}
\usepackage{lmodern}

\addbibresource{references.bib}
\makeindex

\begin{document}

\maketitle
\tableofcontents
\listoffigures
\listoftables

This is \THIS; a \POSIX-compliant \UNIX\ \Shell{} program written in \ANSI-C. This program is written using the \WEB{} literate programming framework.

@*Saving the turtles.\label{sec:saving_the_turtles}

It is true that, for the past handful of decades (nearing 6), the \UNIX\ operating system and its descendants have played a very large role in progress of \textit{Common Computation}. I define this term as the aspects of computational arts which is seldom discussed in academia. The \POSIX\ \Shell{} itself has rarely been subject of academic scrutiny. The clergy don't see any worth in it, because \Shell{}, by design, is a program which is \textit{non-inductive}. It's hard to verify a program whose entire job is to communicate with a system that itself is hard to verify. It's hard to come up with theoretical frameworks about the \UNIX\ \Shell{}. \parencite(felici2024\Shell{}fuzzer) admits this, and it's one of those rare works of clergy on the \Shell{}.

But as we said, \Shell{} is \textit{Common}. \Shell{} is \textit{Pop culture}. \Shell{} is perhaps, one of the earliest \textit{scripting} languages, barring, of course, \Forth\parencite{rather1996evolution}.

It is upon this \textit{lay} foundation that \THIS\ builds itself. \THISs tries not to be a marvel, rather, a spec of dust. One \Shell{} amongst the many.

@*Prelude to \THIS.\label{sec:prelude_to_this}

First, let's use \CWEB's macro capabilities to define three numbers, |NAT_SMALL|, |NAT_MEDIUM| and |NAT_LARGE|. These will be very useful as quantities, and other uses.

@d NAT_SMALL 32
@ |NAT_SMALL| for small quantities;
@d NAT_MEDIUM 128
@ |NAT_MEDIUM| for medium quantities;
@d NAT_LARGE 1024
@ and |NAT_LARGE| for large quantities;

@ Let's set up our program in three sections:

\begin{enumerate}
\item Including necessary runtime and \UNIX-specific header files;
\item Defining constant symbols;
\item Defining necessary types and data structures;
\end{enumerate}

@p

@<Including necessary runtime files@>@/
@<Defining constant symbols@>@/
@<Defining necessary types and data structures@>@/

@ Let's include Standard Library runtime header files. Remember that we are limited to \ANSI-C, this means we don't have access to goodies like |stdbool.h| and |stdint.h|. We'll have to make due.

@<Including necessary runtime files@>=
%START_C_CODE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
%END_C_CODE

@ We now include \UNIX-specific header files$\ldots$

@<Including necessary runtime files@>+=
%START_C_CODE
#include <unistd.h>
#include <signal.h>
#include <limits.h>
#include <syslog.h>
%END_C_CODE

@ We now define several types. Our inagural |typdef| is the |bool_t| type. We define types for integers as well, such as |scalar_t| and |length_t|.

@c @<Defining necessary types and data structures@>=
%START_C_CODE
typedef int bool_t;     /* The bool type */
typedef unsigned long length_t; /* The length type */
typedef double scalar_t; /* The rational type */
typedef int pstat_t; /* Integer holding the Process state */
typedef int jstate_t; /* Integer holding the Job state */
typedef pid_t jid_t; /* The job ID */
typedef char name_t[NAT_SMALL]; /* A `small` character string for names */
%END_C_CODE

@ We shall now define several data structures for \THIS. Our \Shell{} is a proper \POSIX\ \Shell{}. For everything standards-related, we shall follow \parencite{posix2017std}, or \POSIXSTDXCU, which from now on we shall refer to as \XCU. According to \XCU, a \Shell{} may, or may not have \JobControl. To quote \XCU:

\begin{quotation}
[Job control is a] facility that allows users selectively to stop (suspend) the execution of process and continue (resume) their execution at a later point. The user typically employs this facility via the interactive interface jointly supplied by the terminal I/IO driver and command interpreter.
\end{quotation}

So we shall now define a data strcuture (or several) which facilitate \JobControl.

But before that, we must ask ourselves, \textsf{What is a \Shell{} to do$\ldots$?}.

This is indeed an interesting question. We \textit{are} writing a \Shell{} program, are we not?

So let's take a detour and define what we exactly want out of this program. First, let's take a look at the history of \Shell.

@*The history of \Shell{}.\label{sec:a_history_of_shell}

\BellLabs\ was originally located at \StreetAddress{463 West Street, New York City}. But at the beginning of the \WorldWarII, many of its activities moved out of NYC\parencite{kernighan2020unix}. \BellLabs was responsible for advent of the \Transistor. Due to the gripe \BellTelephones\ on wired communications in the \UnitedStates, the government of the US decided to disallow \BellTelephones from ever entering the computer hardware market. This encouraged \BellTelephones\ to enter, or rather, \textit{synthesize} the software market. So they began work on a \TimeSharing\ operating system, \MULTICS, with \MIT. \MULTICS\ failed as a concept. At this time, an employee of \BellLabs\, \KenThompson, found a small mini-computer (a \PDPSeven) and ported \MULTICS\ into it. This was beginning of \UNIX, renamed from \UNICS.

\UNIX\ is a time-sharing operating system for one system. In a time-sharing system, resources are allocated to terminals, most likely connected via 120mA current to a mainframe, and each person logs into their terminal and uses his allotment. \UNIX\ ran on a mini-computer, so those resources went to \textit{processes}, and to manage those processes, \KenThompson\ created the \UNIX\ \Shell{}.

\Shell{} was based on works of his friend and co-worker, \McIlroy, who had was working on dataflow and coroutines at the same time\parencite{mcilroy1968coroutines}. \Shell\ is, technically partially, a \textit{dataflow language}. It leverages \UNIX's \IPCPIPE{}s to pass data along between applications. Although this feature did not come into full fruition until \Bourne\ did a full re-evaluation of \Shell\ in 1978\parencite{bourne1978unix}.

Aftex \UNIX\ was standardized into \POSIX, \Shell, too, was standardized. \GNU's \Bash\ is a free-and-open-source version of the \Bourne\ shell. Other \POSIX\ shells include \Zsh, \Mksh, and \Dash.

@*How does \Shell\ operate? (Part \Roman{1}).\label{sec:how_does_shell_operate_part_1}

"The Shell" is the most visible system interface in \Unix\parencite{mcilroy1978foreword}. \Shell\ is used to combine programs. In a way, \Shell\ is a \textit{Program-flow manager}.

This program is either \textit{interacted with} or \textit{batched off}. The correct verbage for 'batching off' is a \textit{Shell script}. The correct terminology for 'interacted with' is \textit{Interactive session}.

I am personally an avid user of \Fish\ shell. It has a different syntax that \POSIX's which we shall be making, but it's nonetheless, a shell designed for interactive use. The syntax for \Fish\ is, most often, identical with \POSIX's. So, to launch my text editor (\NeoVim) to edit this document, I type in:

\begin{ShellScript}{interactive}
neovim /mnt/manifest/\jobname.w
\end{ShellScript}

This is the simplest way one could utilize \Shell. Let's look at a more complex usage (\textit{slightly} more!) of \Shell:

\begin{ShellScript}{interactive}
for i in {1, 2, 3}; do echo \$i; done
\end{ShellScript}

This program prints these three numbers. \Util{echo} is a \Utility; it is not a \Function; unless you override it that is. We have utils like \Util{rm}, \Util{mv}, and \Util{cp}. But if you define a \Function\ with thiese names, they shadow over.

Now, this not a \Shell\ tutorial, and as for syntax and grammar, we'll talk about it in \ref{sec:syntax_and_grammar_of_shell}. So for now, this shall suffice to give you an idea of how a shell operation is done.

So when we pass something like \InlineShell{ls -a .} to our shell \Interpreter{} (we'll talk about this concept later!), it will list all the files and subdirectories, plus the information about those files, in the \REPL. Unless shadowed by a \Function, here, \Util{ls} is a utility.

When we type that, and press \KEnter, what happens in the backend is called a \FEWL. What is a \FEWL? We, of course, must implement it later. But at the moment, what we want to do is defining data structues that facilitates, among many things, a \FEWL. So let's define the |Process| structure.

@**Defining the \Process{} data structure.\label{sec:defining_process_struct}

@c @<Defining necessary types and...@>+=
/* Let's define out first structure already! */
%START_C_CODE
typedef struct Process {
   pid_t system_id;     /* ID of this process in system */
   int internal_id;     /* Our ID for this process */
   pstat_t current_state; /* Current status */
   int fno_in,
       fno_out,
       fno_err;    /* File descriptors for input, output and error */
   bool_t is_lead; /* Is this a 'lead' in a pipeline? */
   bool_t is_bkrnd; /* Is this a 'background' process? */
} Process;
%END_C_CODE

@ So, all these fields are self-explanatory and if you don't understand any of them don't worry --- \textit{We shall explain}.

Some of these values flag, and some enumerate. Of those who enumerate, |current_state| does so for the internal status of the process, values of which we saw in \ref{sec:enumerative_defines}. Flaggers; |is_lead| basically flags it if the process is a \textit{lead} in a \Pipeline, a concept we shall explain in \ref{sec:explaining_pipelines}; and |is_bkgrnd| flags if the process has been sent to the backgound, part of \JobControl. We explain job control in \ref{sec:explaining_job_control}.

@**Defining the \Job{} data structure.\label{sec:defining_job_struct}

Our subsequent data structure to be defined is |Job|. The |Job| data structure is used in \JobControl. Keep in mind that job control is optional, according to \XCU. It is enabled by default, but the \CmdlineSwitch{m} switch turns it off.

@c @<Defining necessary types and...@>+=
%START_C_CODE
typedef struct Job {
  jid_t  internal_id;   /* The internal ID for this job */
  name_t internal_name; /* The internal name for the job */
  jstate_t current_state; /* The current status of this job */
  Process *processes;   /* The processes for this job */
} Job;
%END_C_CODE

This was |Job|. A small note on |internal_name|; this name is rarely used outside of internal utilities like \InternalUtility{qselect} and \InternalUtility{qsub}, at least according to the \XCU. The name of a job is most likely used in context of \textit{batch jobs} (see \ref{sec:explaining_job_control}).

Speaking of names, we really need a place to store them, don't we? And we also need a data structure, |Symbol|, to give \textit{meaning} to names. A name, by itself, is meaningless. A name might refer to a \Job{}, but as we'll see in \ref{sec:shell_variables} --- and \Variable{}s are just an example, a name could have several \textit{semantics}.

@**Defining the \Symbol{} data structure.\label{sec:defining_symbol_struct}

To handle the name issue, we must define a \Symbol\ data structure.

@c @<Defining necessary types and...@>+=
%START_C_CODE
typedef struct Symbol {
   symid_t internal_id;  /* The internal ID of this symbol */
   name_t symbol_name;  /* The symbol name */
   symkind_t symbol_kind; /* The symbol kind */
   union {
    Job *v_job; /* A Job symbol */
    /*  TODO ... */
   };
} Symbol;
%END_C_CODE

%%% END OF PROGRAM %%%
@

\newpage
\printindex

\newpage
\printbibliography

\begin{filecontents}{references.bib}
@@techreport{mcilroy1978foreword,
  title={The Bell System Technical Journal Foreword},
  author={McIlroy, M.D. and Pinson, E.N. and Tague, B.A.},
  year={July-August 1978},
  volume={57},
  publisher={Bell Labs}
}
@@article{bourne1978unix,
  title={UNIX time-sharing system: The UNIX shell},
  author={Bourne, Stephen Richard},
  journal={The Bell System Technical Journal},
  volume={57},
  number={6},
  pages={1971--1990},
  year={1978},
  publisher={Nokia Bell Labs}
}
@@techreport{mcilroy1968coroutines,
  author      = {M. D. McIlroy},
  title       = {Coroutines},
  institution = {Bell Telephone Laboratories},
  year        = {1968},
  address     = {Murray Hill, New Jersey},
  type        = {Technical report},
}
@@book{kernighan2020unix,
  title={UNIX: A History and a Memoir},
  author={Kernighan, Brian W},
  year={2020},
  publisher={Kindle Direct Publishing Seattle, WA}
}
@@techreport{posix2017std
  type={Standard},
  key={IEEE 1003.1(TM)}
  year={2017}
  title={IEEE Standard for Information Technology Portable Operating System Interface (POSIX(R))
}
  institution={IEEE}}
@@incollection{rather1996evolution,
  title={The evolution of Forth},
  author={Rather, Elizabeth D and Colburn, Donald R and Moore, Charles H},
  booktitle={History of programming languages---II},
  pages={625--670},
  year={1996}
}
@@article{felici2024shellfuzzer,
  title={Shell Fuzzer: Grammar-based Fuzzing of Shell Interpreters},
  author={Felici, Riccardo and Pozzi, Laura and Furia, Carlo A},
  journal={arXiv preprint arXiv:2408.00433},
  year={2024}
}
@@incollection{ritchie1996development,
  title={The development of the C programming language},
  author={Ritchie, Dennis M},
  booktitle={History of Programming languages---II},
  pages={671--698},
  year={1996}
}
@@book{kernighan1988c,
  title={The C programming language},
  author={Kernighan, Brian W and Ritchie, Dennis M},
  year={1988},
  publisher={prentice-Hall}
}
\end{filecontents}

\end{document}