Changeset 195f43d for doc/theses/mike_brooks_MMath/string.tex
- Timestamp:
- Mar 13, 2025, 9:21:17 AM (13 days ago)
- Branches:
- master
- Children:
- 3bd9508
- Parents:
- 3483185
- File:
-
- 1 edited
-
doc/theses/mike_brooks_MMath/string.tex (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
TabularUnified doc/theses/mike_brooks_MMath/string.tex ¶
r3483185 r195f43d 1 1 \chapter{String} 2 2 3 \vspace*{-20pt} 3 4 This chapter presents my work on designing and building a modern string type in \CFA. 4 The discussion starts with examples of interesting string problems, followed by examples of how these issues are solved in my design.5 The discussion starts with examples of interesting string problems, followed by examples of how these issues are resolved in my design. 5 6 6 7 … … 8 9 9 10 To prepare for the following discussion, comparisons among C, \CC, Java and \CFA strings are presented, beginning in \VRef[Figure]{f:StrApiCompare}. 10 It provides a classic ``cheat sheet'' presentation, summarizing the names of the typical operations. 11 12 \begin{figure} 11 It provides a classic ``cheat sheet'' presentation, summarizing the names of the most common closely-equivalent operations. 12 The over-arching commonality is that operations work on groups of characters for assigning, copying, scanning, and updating. 13 14 \begin{figure}[h] 13 15 \begin{cquote} 14 16 \begin{tabular}{@{}l|l|l|l@{}} … … 34 36 \end{figure} 35 37 36 The key commonality is that operations work on groups of characters for assigning, copying, scanning, and updating. 37 Because a C string is null terminated and requires explicit storage management \see{\VRef{s:String}}, most of its group operations are error prone and expensive.38 Most high-level string libraries use a separate length field and specialized storage management to support group operations.39 \CC strings retain null termination to interface with library functions requiring C strings.40 \begin{cfa} 41 int open( const char * pathname, int flags );38 As mentioned in \VRef{s:String}, a C string differs from other string types as it uses null termination rather than a length, which leads to explicit storage management; 39 hence, most of its group operations are error prone and expensive. 40 Most high-level string libraries use a separate length field and specialized storage management to implement group operations. 41 Interestingly, \CC strings retain null termination just in case it is needed to interface with C library functions. 42 \begin{cfa} 43 int open( @const char * pathname@, int flags ); 42 44 string fname{ "test.cc" ); 43 45 open( fname.@c_str()@, O_RDONLY ); 44 46 \end{cfa} 45 The function @c_str@does not create a new null-terminated C string from the \CC string, as that requires passing ownership of the C string to the caller for eventual deletion.\footnote{47 Here, the \CC @c_str@ function does not create a new null-terminated C string from the \CC string, as that requires passing ownership of the C string to the caller for eventual deletion.\footnote{ 46 48 C functions like \lstinline{strdup} do return allocated storage that must be freed by the caller.} 47 Instead, each \CC string is null terminated just in case it might be needed for this purpose.49 % Instead, each \CC string is null terminated just in case it might be needed for this purpose. 48 50 Providing this backwards compatibility with C has a ubiquitous performance and storage cost. 49 51 50 While \VRef[Figure]{f:StrApiCompare} emphasizes cross-language similarities, it elides differences in how a certain function is used. 51 For example, the @replace@ function in \CC performs a modification on its @this@ parameter, while the Java one allocates and returns a new string with the result, leaving @this@ unmodified. 52 While \VRef[Figure]{f:StrApiCompare} emphasizes cross-language similarities, it elides many specific operational differences. 53 For example, the @replace@ function selects a substring in the target and substitutes it with the source string, which can be smaller or larger than the substring. 54 \CC performs the modification on the mutable receiver object. 55 \begin{cfa} 56 string s1 = "abcde"; 57 s1.replace( 2, 3, "xy" ); $\C[2.25in]{// replace by position (zero origin) and length, mutable}\CRT$ 58 cout << s1 << endl; 59 $\texttt{abxy}$ 60 \end{cfa} 61 while Java allocates and returns a new string with the result, leaving the receiver unmodified. 62 \begin{java} 63 String s = "abcde"; 64 String r = s.replace( "cde", "xy" ); $\C[2.25in]{// replace by text, immutable}$ 65 StringBuffer sb = new StringBuffer( "abcde" ); 66 sb.replace( 2, 5, "xy" ); $\C{// replace by position, mutable}\CRT$ 67 System.out.println( s + ' ' + r + ' ' + sb ); 68 $\texttt{abcde abxy abxy}$ 69 \end{java} 52 70 Generally, Java's @String@ type is immutable. 53 Java provides a @StringBuffer@ near-analog that is mutable, but the differences are significant; for example, this class's @substring@ functions still return copies rather than mutable selections. 54 55 These more significant differences are summarized in \VRef[Figure]{f:StrSemanticCompare}. It calls out the consequences of each language taking a different approach on the ``internal'' issues, like storage management and null-terminator interoperability. The discussion following justifies the figure's yes/no entries. 56 57 \begin{figure} 58 \begin{tabular}{@{}p{0.5in}p{2in}p{2in}>{\centering\arraybackslash}p{0.2in}>{\centering\arraybackslash}>{\centering\arraybackslash}p{0.2in}>{\centering\arraybackslash}p{0.2in}>{\centering\arraybackslash}p{0.2in}@{}} 59 & & & \multicolumn{4}{c}{\underline{Supports Helpful?}} \\ 71 Java provides a @StringBuffer@ near-analog that is mutable, but the differences are significant; for example, @StringBuffer@'s @substring@ functions still return copies rather than mutable selections. 72 Finally, the operations between these type are asymmetric, \eg @string@ has @replace@ by text but not replace by position and vice versa for @StringBuffer@. 73 74 More significant operational differences relate to storage management, often appearing through assignment (@target = source@), and are summarized in \VRef[Figure]{f:StrSemanticCompare}. 75 % It calls out the consequences of each language taking a different approach on ``internal'' storage management. 76 The following discussion justifies the figure's yes/no entries per language. 77 78 \begin{figure} 79 \setlength{\extrarowheight}{2pt} 80 \begin{tabularx}{\textwidth}{@{}p{0.6in}XXcccc@{}} 81 & & & \multicolumn{4}{@{}c@{}}{\underline{Supports Helpful?}} \\ 60 82 & Required & Helpful & C & \CC & Java & \CFA \\ 61 83 \hline 62 84 Type abst'n 63 & Low-level: A ``string'' type represents a varying amount of text that is communicated with a function as a parameter/return.64 & High-level: Using a string-typed variable relieves the user of managing a distinct allocationfor the text.65 & \xmark & \cmark & \cmark & \cmark\\85 & Low-level: The string type is a varying amount of text communicated via a parameter or return. 86 & High-level: The string-typed relieves the user of managing memory for the text. 87 & no & yes & yes & yes \\ 66 88 \hline 67 \multirow{2}{0.5in} 68 {State} 89 State 69 90 & \multirow{2}{2in} 70 {Fast Initialize: The target receives the characters of the original, but no time is spent copying characters. The result is one ofAlias or Snapshot.}71 & Alias: The target is a further name for the text in the original; changes made in either variable are visible in both.72 & \cmark & \cmark & \xmark & \cmark\\91 {Fast Initialize: The target receives the characters of the source without copying the characters, resulting in an Alias or Snapshot.} 92 & Alias: The target name is within the source text; changes made in either variable are visible in both. 93 & yes & yes & no & yes \\ 73 94 \cline{3-7} 74 95 & 75 & Snapshot: The target (resp.\ source) contains the value of the source at the time of the initialization until the target (resp.\ source) is explicitly changed.76 & \xmark & \xmark & \cmark & \cmark\\96 & Snapshot: The target is an alias within the source until the target changes (copy on write). 97 & no & no & yes & yes \\ 77 98 \hline 78 99 Symmetry 79 & Laxed: The target ’s type is anything string-like; it may have a different status concerning ownership.80 & Strict: The target ’s type is the same as the original; both strings are equivalent peers concerning ownership.81 & -- & \xmark & \cmark & \cmark\\100 & Laxed: The target's type is anything string-like; it may have a different status concerning ownership. 101 & Strict: The target's type is the same as the source; both strings are equivalent peers concerning ownership. 102 & -- & no & yes & yes \\ 82 103 \hline 83 104 Referent 84 & Variable-Constrained: The target can accept the entire text of the original.85 & Fragment: The target can accept an arbitrary substring of the original.86 & \xmark & \xmark & \cmark & \cmark87 \end{tabular }105 & Variable-Constrained: The target can accept the entire text of the source. 106 & Fragment: The target can accept an arbitrary substring of the source. 107 & no & no & yes & yes 108 \end{tabularx} 88 109 89 110 \noindent 90 111 Notes 91 \begin{itemize} 112 \begin{itemize}[parsep=0pt] 92 113 \item 93 114 All languages support Required in all criteria. … … 95 116 A language gets ``Supports Helpful'' in one criterion if it can do so without sacrificing the Required achievement on all other criteria. 96 117 \item 97 The C ``string'' is @char *@, under the conventions that @<string.h>@ requires. Symmetry is not applicable to C.118 The C ``string'' is actually @char []@, under the conventions that @<string.h>@ requires. Hence, there is no actual string type in C, so symmetry does not apply. 98 119 \item 99 120 The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to @C++@. 100 121 \end{itemize} 101 \caption{Comparison of languages' strings, assignment-semanticsperspective.}122 \caption{Comparison of languages' strings, storage management perspective.} 102 123 \label{f:StrSemanticCompare} 103 124 \end{figure} 104 125 105 In C: 106 \begin{cfa} 107 char * s1 = ...; // assumed 108 char * s2 = s1; // alias state, variable-constrained referent 109 char * s3 = s1 + 2; // alias state, variable-constrained referent 110 \end{cfa} 111 The issue of symmetry is trivial for a low-level type, and so, scored as not applicable to C. 112 With the type not managing the text buffer, there is no ownership question, \ie nothing done with the @s1@ or @s2@ variables leads to the memory that their text currently occupies becoming reusable. 113 While @s3@ is a valid C-string that contains a proper substring of @s1@, the @s3@ technique does not constitue having a fragment referent because null termination implies the substring cannot be chosen arbitrarily; the technique works only for suffixes. 114 115 In \CC: 116 \begin{cfa} 117 string s1 = ...; // assumed 118 string & s2 = s1; // alias state, lax symmetry, variable-constrained referent 119 string s3 = s1; // NOT fast-initialize (strict symmetry, variable-constrained referent) 120 string s4 = s1.substr(2,4); // NOT fast-initialize (strict symmetry, fragment referent) 121 string & s5 = s1.substr(2,4); // memory-use error 122 \end{cfa} 123 The lax symmetry of the @s2@ technique reflects how the validity of @s2@ depends on the lifetime of @s1@. 124 It is common practice in \CC to use the @s2@ technique for parameter passing, but the safest-bet advice has to be that the callee can only use the referenced string for the duration of the call. 125 So, when the called function is a constructor, it is typical that the implementation is doing an @s3@-style initialization of a string-object-typed member. 126 Exceptions of this pattern are possible, of course, but they represent the programmer taking responsiblity to assure safety where the type system does not. 127 The @s4@ initialization is constrained by specification to copy the substring because of @c_str@ being specified to be a null-terminated character run that is not its own allocation. 128 TODO: address caveat that @s3@ could be done fast by reference counting in the text area. 129 130 131 In Java: 132 \begin{cfa} 133 String s1 = ...; // assumed 134 String s2 = s1; // snapshot state, strict symmetry, variable-constrained referent 135 String s3 = s1.substring(2,4); // snapshot state (possible), strict symmetry, fragment referent 136 \end{cfa} 137 Here, facts about Java's implicit pointers and pointer equality can overcomplicate the picture. 138 The further fact of Java's string immutability means that string variables behave as simple values. 139 The result in @s2@ is the value of @s1@, and their pointer equality certainly assures that no time is spent copying characters. 140 With @s3@, the case for fast-copy is more subtle. 141 Certainly, its value is not pointer-equal to @s1@, implying at least a further allocation. 126 In C, the declaration 127 \begin{cfa} 128 char s[$\,$] = "abcde"; 129 \end{cfa} 130 creates a second-class fixed-sized string-variable, as it can only be used in its lexical context; 131 it cannot be passed by value to string operations or user functions as C array's cannot be copied because there is no string-length information passed to the function. 132 Therefore, only pointers to strings are first-class, and discussed further. 133 \begin{cfa} 134 (const) char * s = "abcde"; $\C[2.25in]{// alias state, n/a symmetry, variable-constrained referent}$ 135 char * s1 = s; $\C{// alias state, n/a symmetry, variable-constrained referent}$ 136 char * s2 = s; $\C{// alias state, n/a symmetry, variable-constrained referent}$ 137 char * s3 = &s[1]; $\C{// alias state, n/a symmetry, variable-constrained referent}$ 138 char * s4 = &s3[1]; $\C{// alias state, n/a symmetry, variable-constrained referent}\CRT$ 139 printf( "%s %s %s %s %s\n", s, s1, s2, s3, s4 ); 140 $\texttt{\small abcde abcde abcde bcde cde}$ 141 \end{cfa} 142 Note, all of these strings rely on the single null termination character at the end of @s@. 143 The issue of symmetry does not apply to C strings because the value and pointer strings are essentially different types, and so this feature is scored as not applicable for C. 144 With the type not managing the text buffer, there is no ownership question, \ie operations on @s1@ or @s2@ never leads to their memory becoming reusable. 145 While @s3@ is a valid C-string that contains a proper substring of @s1@, the @s3@ technique does not constitute having a fragment referent because null termination implies the substring cannot be chosen arbitrarily; the technique works only for suffixes. 146 147 In \CC, @string@ offers a high-level abstraction. 148 \begin{cfa} 149 string s = "abcde"; 150 string & s1 = s; $\C[2.25in]{// alias state, lax symmetry, variable-constrained referent}$ 151 string s2 = s; $\C{// copy (strict symmetry, variable-constrained referent)}$ 152 string s3 = s.substr( 1, 2 ); $\C{// copy (strict symmetry, fragment referent)}$ 153 string s4 = s3.substr( 1, 1 ); $\C{// copy (strict symmetry, fragment referent)}$ 154 cout << s << ' ' << s1 << ' ' << s2 << ' ' << s3 << ' ' << s4 << endl; 155 $\texttt{\small abcde abcde abcde bc c}$ 156 string & s5 = s.substr(2,4); $\C{// error: cannot point to temporary}\CRT$ 157 \end{cfa} 158 The lax symmetry reflects how the validity of @s1@ depends on the content and lifetime of @s@. 159 It is common practice in \CC to use the @s1@-style pass by reference, with the understanding that the callee only use the referenced string for the duration of the call, \ie no side-effect using the parameter. 160 So, when the called function is a constructor, it is typical to use an @s2@-style copy initialization to string-object-typed member. 161 Exceptions to this pattern are possible, but require the programmer to assure safety where the type system does not. 162 The @s3@ initialization is constrained to copy the substring because @c_str@ always provides a null-terminated character, which is different from source string. 163 @s3@ assignment could be fast by reference counting the text area and using copy-on-write, but would require an implementation upgrade. 164 165 In Java, @String@ also offers a high-level abstraction: 166 \begin{cfa} 167 String s = "abcde"; 168 String s1 = s; $\C[2.25in]{// snapshot state, strict symmetry, variable-constrained referent}$ 169 String s2 = s.substring( 1, 3 ); $\C{// snapshot state (possible), strict symmetry, fragment referent}$ 170 String s3 = s2.substring( 1, 2 ); $\C{// snapshot state (possible), strict symmetry, fragment referent}\CRT$ 171 System.out.println( s + ' ' + s1 + ' ' + s2 + ' ' + s3 ); 172 System.out.println( (s == s1) + " " + (s == s2) + " " + (s2 == s3) ); 173 $\texttt{\small abcde abcde bc c}$ 174 $\texttt{\small true false false}$ 175 \end{cfa} 176 Note, @substring@ takes a start and end position, rather than a start position and length. 177 Here, facts about Java's implicit pointers and pointer equality can over complicate the picture, and so are ignored. 178 Furthermore, Java's string immutability means string variables behave as simple values. 179 The result in @s1@ is the pointer in @s@, and their pointer equality confirm no time is spent copying characters. 180 With @s2@, the case for fast-copy is more subtle. 181 Certainly, its value is not pointer-equal to @s@, implying at least a further allocation. 142 182 TODO: finish the fast-copy case. 143 Java strings lacking mutation means that aliasing is notpossible with the @String@ type.183 Java's immutable strings mean aliasing is impossible with the @String@ type. 144 184 Java's @StringBuffer@ provides aliasing, though without supporting symmetric treatment of a fragment referent; as a result, @StringBuffer@ scores as \CC. 145 185 The easy symmetry that the Java string enjoys is aided by Java's garbage collection; Java's @s2@ is doing effectively the operation of \CC's @s2@, though without the consequence to of complicating memory management. 146 186 147 Finally, in \CFA, 148 \begin{cfa} 149 string s1 = ...; // assumed 150 string s2 = s1; // snapshot state, strict symmetry, variable-constrained referent 151 string s3 = s1`shareEdits; // alias state, strict symmetry, variable-constrained referent 152 string s4 = s1(2,4); // snapshot state, strict symmetry, fragment referent 153 string s5 = s1(2,4)`shareEdits; // alias state, strict symmetry, fragment referent 154 \end{cfa} 155 all helpful criteria of \VRef[Figure]{f:StrSemanticCompare} are satisfied. 156 The \CFA string manages storage, handles all assignments, including those of fragment referents, with fast initialization, provides the choice between snapshot and alias semantics, does so symmetrically with one type (which assures text validity according to the lifecycles of the string variables). 187 Finally, In \CFA, @string@ also offers a high-level abstraction: 188 \begin{cfa} 189 string s = "abcde"; 190 string & s1 = s; $\C[2.25in]{// alias state, strict symmetry, variable-constrained referent}$ 191 string s2 = s; $\C{// snapshot state, strict symmetry, variable-constrained referent}$ 192 string s3 = s`shareEdits; $\C{// alias state, strict symmetry, variable-constrained referent}\CRT$ 193 string s4 = s( 1, 2 ); 194 string s5 = s4( 1, 1 ); 195 sout | s | s1 | s2 | s3 | s4 | s5; 196 $\texttt{\small abcde abcde abcde abcde bc c}$ 197 \end{cfa} 198 % all helpful criteria of \VRef[Figure]{f:StrSemanticCompare} are satisfied. 199 The \CFA string manages storage, handles all assignments, including those of fragment referents with fast initialization, provides the choice between snapshot and alias semantics, and does so symmetrically with one type (which assures text validity according to the lifecycles of the string variables). 157 200 With aliasing, the intuition is that each string is an editor on an open shared document. 158 With fragment aliasing, the intuition is that these editor views have been sc olled or zoomed to overlapping, but potentially different, ranges.201 With fragment aliasing, the intuition is that these editor views have been scrolled or zoomed to overlapping, but potentially different, ranges. 159 202 160 203 The remainder of this chapter explains how the \CFA string achieves this usage style. … … 243 286 Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined). 244 287 A constructor is a user-defined function run implicitly \emph{after} an object's declaration-storage is created, and a destructor is a user-defined function run \emph{before} an object's declaration-storage is deleted. 245 This feature, called RAII~\cite[p.~389]{Stroustrup94}, guarantees pre 288 This feature, called RAII~\cite[p.~389]{Stroustrup94}, guarantees pre-invariants for users before accessing an object and post invariants for the programming environment after an object terminates. 246 289 247 290 The purposes of these invariants goes beyond ensuring authentic values inside an object.
Note: See TracChangeset
for help on using the changeset viewer.
