[27f1055] | 1 | \chapter{Introduction} |
---|
| 2 | |
---|
[bdc8591] | 3 | All modern programming languages provide three high-level containers (collection): array, linked, and string. |
---|
| 4 | Often array is part of the programming language, while linked is built from pointer types, and string from a combination of array and linked. |
---|
| 5 | |
---|
[19a2890] | 6 | \cite{Blache19} |
---|
| 7 | \cite{Oorschot23} |
---|
| 8 | \cite{Ruef19} |
---|
| 9 | |
---|
[bdc8591] | 10 | \section{Array} |
---|
| 11 | |
---|
| 12 | Array provides a homogeneous container with $O(1)$ access to elements using subscripting. |
---|
| 13 | The array size can be static, dynamic but fixed after creation, or dynamic and variable after creation. |
---|
| 14 | For static and dynamic-fixed, an array can be stack allocated, while dynamic-variable requires the heap. |
---|
| 15 | |
---|
| 16 | |
---|
| 17 | \section{Linked List} |
---|
| 18 | |
---|
| 19 | Linked provides a homogeneous container with $O(log N)$/$O(N)$ access to elements using successor and predecessor operations. |
---|
| 20 | Subscripting by value is sometimes available. |
---|
| 21 | Linked types are normally dynamically sized by adding/removing node using link fields internal or external to the elements (nodes). |
---|
| 22 | If a programming language allows pointer to stack storage, linked types can be allocated on the stack; |
---|
| 23 | otherwise, elements are heap allocated and explicitly/implicitly managed. |
---|
| 24 | |
---|
| 25 | |
---|
| 26 | \section{String} |
---|
| 27 | |
---|
| 28 | String provides a dynamic array of homogeneous elements, where the elements are often human-readable characters. |
---|
| 29 | What differentiates string from other types in that string operations work on blocks of elements for scanning and changing the elements, rather than accessing individual elements. |
---|
| 30 | Nevertheless, subscripting is often available. |
---|
| 31 | The cost of string operations is less important than the power of the block operation to accomplish complex manipulation. |
---|
| 32 | The dynamic nature of string means storage is normally heap allocated but often implicitly managed, even in unmanaged languages. |
---|
| 33 | |
---|
| 34 | |
---|
| 35 | \section{C/\CFA} |
---|
| 36 | |
---|
| 37 | The goal of this work is to introduce safe and complex versions of array, link, and string into the programming language \CFA, which based on the C. |
---|
| 38 | |
---|
| 39 | |
---|
| 40 | \subsection{Common knowledge} |
---|
| 41 | |
---|
| 42 | The reader is assumed to have used C or \CC for the coursework of at least four university-level courses, or have equivalent experience. |
---|
| 43 | The current discussion introduces facts, unaware of which, such a functioning novice may be operating. |
---|
| 44 | |
---|
| 45 | % TODO: decide if I'm also claiming this collection of facts, and test-oriented presentation is a contribution; if so, deal with (not) arguing for its originality |
---|
| 46 | |
---|
| 47 | \subsection{Convention: C is more touchable than its standard} |
---|
| 48 | |
---|
| 49 | When it comes to explaining how C works, I like illustrating definite program semantics. |
---|
| 50 | I prefer doing so, over a quoting manual's suggested programmer's intuition, or showing how some compiler writers chose to model their problem. |
---|
| 51 | To illustrate definite program semantics, I devise a program, whose behaviour exercises the point at issue, and I show its behaviour. |
---|
| 52 | |
---|
| 53 | This behaviour is typically one of |
---|
| 54 | \begin{itemize} |
---|
| 55 | \item my statement that the compiler accepts or rejects the program |
---|
| 56 | \item the program's printed output, which I show |
---|
| 57 | \item my implied assurance that its assertions do not fail when run |
---|
| 58 | \end{itemize} |
---|
| 59 | |
---|
| 60 | The compiler whose program semantics is shown is |
---|
| 61 | \begin{cfa} |
---|
| 62 | $ gcc --version |
---|
| 63 | gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 |
---|
| 64 | \end{cfa} |
---|
| 65 | running on Architecture @x86_64@, with the same environment targeted. |
---|
| 66 | |
---|
| 67 | Unless explicit discussion ensues about differences among compilers or with (versions of) the standard, it is further implied that there exists a second version of GCC and some version of Clang, running on and for the same platform, that give substantially similar behaviour. |
---|
| 68 | In this case, I do not argue that my sample of major Linux compilers is doing the right thing with respect to the C standard. |
---|
| 69 | |
---|
| 70 | |
---|
| 71 | \subsection{C reports many ill-typed expressions as warnings} |
---|
| 72 | |
---|
| 73 | These attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed. |
---|
| 74 | \lstinput{12-15}{bkgd-c-tyerr.c} |
---|
| 75 | with warnings: |
---|
| 76 | \begin{cfa} |
---|
| 77 | warning: assignment to 'float *' from incompatible pointer type 'void (*)(void)' |
---|
| 78 | warning: assignment to 'void (*)(void)' from incompatible pointer type 'float *' |
---|
| 79 | \end{cfa} |
---|
| 80 | Similarly, |
---|
| 81 | \lstinput{17-19}{bkgd-c-tyerr.c} |
---|
| 82 | with warning: |
---|
| 83 | \begin{cfa} |
---|
| 84 | warning: passing argument 1 of 'f' from incompatible pointer type |
---|
| 85 | note: expected 'void (*)(void)' but argument is of type 'float *' |
---|
| 86 | \end{cfa} |
---|
| 87 | with a segmentation fault at runtime. |
---|
| 88 | |
---|
| 89 | That @f@'s attempt to call @g@ fails is not due to 3.14 being a particularly unlucky choice of value to put in the variable @pi@. |
---|
| 90 | Rather, it is because obtaining a program that includes this essential fragment, yet exhibits a behaviour other than "doomed to crash," is a matter for an obfuscated coding competition. |
---|
| 91 | |
---|
| 92 | A "tractable syntactic method for proving the absence of certain program behaviours by classifying phrases according to the kinds of values they compute"*1 rejected the program. |
---|
| 93 | The behaviour (whose absence is unprovable) is neither minor nor unlikely. |
---|
| 94 | The rejection shows that the program is ill-typed. |
---|
| 95 | |
---|
| 96 | Yet, the rejection presents as a GCC warning. |
---|
| 97 | |
---|
| 98 | In the discussion following, ``ill-typed'' means giving a nonzero @gcc -Werror@ exit condition with a message that discusses typing. |
---|
| 99 | |
---|
| 100 | *1 TAPL-pg1 definition of a type system |
---|
[27f1055] | 101 | |
---|
| 102 | |
---|
| 103 | \section{Contributions} |
---|
[bdc8591] | 104 | |
---|
| 105 | \subsection{Linked List} |
---|
| 106 | |
---|
| 107 | \subsection{Array} |
---|
| 108 | |
---|
| 109 | \subsection{String} |
---|