1 | \chapter{Introduction} |
---|
2 | |
---|
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 | |
---|
6 | \cite{Blache19} |
---|
7 | \cite{Oorschot23} |
---|
8 | \cite{Ruef19} |
---|
9 | |
---|
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 |
---|
101 | |
---|
102 | |
---|
103 | \section{Contributions} |
---|
104 | |
---|
105 | \subsection{Linked List} |
---|
106 | |
---|
107 | \subsection{Array} |
---|
108 | |
---|
109 | \subsection{String} |
---|