Changeset 5e8d75bb for doc/theses/mike_brooks_MMath/string.tex
- Timestamp:
- Feb 12, 2025, 1:19:47 PM (6 weeks ago)
- Branches:
- master
- Children:
- 53f4b55
- Parents:
- a8404d9
- File:
-
- 1 edited
-
doc/theses/mike_brooks_MMath/string.tex (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
TabularUnified doc/theses/mike_brooks_MMath/string.tex ¶
ra8404d9 r5e8d75bb 7 7 \section{String Operations} 8 8 9 To prepare for the following discussion, a simple comparison among C, \CC, and \CFA basic string operation is presented. 9 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} 10 13 \begin{cquote} 11 \begin{tabular}{@{}l|l|l @{}}12 C @char [ ]@ & \CC @string@ & \CFA @string@ \\14 \begin{tabular}{@{}l|l|l|l@{}} 15 C @char [ ]@ & \CC @string@ & Java @String@ & \CFA @string@ \\ 13 16 \hline 14 @strcpy@, @strncpy@ & @=@ & @=@ \\ 15 @strcat@, @strncat@ & @+@ & @+@ \\ 16 @strcmp@, @strncmp@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\ 17 @strlen@ & @length@ & @size@ \\ 18 @[ ]@ & @[ ]@ & @[ ]@ \\ 19 & @substr@ & @substr@ \\ 20 & @replace@ & @=@ \emph{(on a substring)}\\ 21 @strstr@ & @find@, @rfind@ & @find@, MISSING \\ 22 @strcspn@ & @find_first_of@, @find_last_of@ & @include@, MISSING \\ 23 @strspn@ & @find_first_not_of@, @find_last_not_of@ & @exclude@, MISSING \\ 24 & @c_str@ & MISSING \\ 17 @strcpy@, @strncpy@ & @=@ & @=@ & @=@ \\ 18 @strcat@, @strncat@ & @+@ & @+@ & @+@ \\ 19 @strcmp@, @strncmp@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ 20 & @equals@, @compareTo@ 21 & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\ 22 @strlen@ & @length@, @size@ & @length@ & @size@ \\ 23 @[ ]@ & @[ ]@ & @charAt@ & @[ ]@ \\ 24 @strncpy@ & @substr@ & @substring@ & @( )@ \\ 25 @strncpy@ & @replace@ & @replace@ & @=@ \emph{(on a substring)}\\ 26 @strstr@ & @find@ & @indexOf@ & @find@ \\ 27 @strcspn@ & @find_first_of@ & @matches@ & @include@ \\ 28 @strspn@ & @find_first_not_of@ & @matches@ & @exclude@ \\ 29 n/a & @c_str@, @data@ & n/a & @strcpy@, @strncpy@ \\ 25 30 \end{tabular} 26 31 \end{cquote} 27 The key commonality is that operations work on groups of characters for assigning. copying, scanning, and updating. 32 \caption{Comparison of languages' strings, API/``cheat-sheet'' perspective.} 33 \label{f:StrApiCompare} 34 \end{figure} 35 36 The key commonality is that operations work on groups of characters for assigning, copying, scanning, and updating. 28 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. 29 38 Most high-level string libraries use a separate length field and specialized storage management to support group operations. … … 32 41 int open( const char * pathname, int flags ); 33 42 string fname{ "test.cc" ); 34 open( fname.@c_str()@ );43 open( fname.@c_str()@, O_RDONLY ); 35 44 \end{cfa} 36 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{ 37 46 C functions like \lstinline{strdup} do return allocated storage that must be freed by the caller.} 38 Instead, each \CC string is null terminat orjust in case it might be needed for this purpose.47 Instead, each \CC string is null terminated just in case it might be needed for this purpose. 39 48 Providing this backwards compatibility with C has a ubiquitous performance and storage cost. 49 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 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?}} \\ 60 & Required & Helpful & C & \CC & Java & \CFA \\ 61 \hline 62 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 allocation for the text. 65 & \xmark & \cmark & \cmark & \cmark \\ 66 \hline 67 \multirow{2}{0.5in} 68 {State} 69 & \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 of Alias 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 \\ 73 \cline{3-7} 74 & 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 \\ 77 \hline 78 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 \\ 82 \hline 83 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 & \cmark 87 \end{tabular} 88 89 \noindent 90 Notes 91 \begin{itemize} 92 \item 93 All languages support Required in all criteria. 94 \item 95 A language gets ``Supports Helpful'' in one criterion if it can do so without sacrificing the Required achievement on all other criteria. 96 \item 97 The C ``string'' is @char *@, under the conventions that @<string.h>@ requires. Symmetry is not applicable to C. 98 \item 99 The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to @C++@. 100 \end{itemize} 101 \caption{Comparison of languages' strings, assignment-semantics perspective.} 102 \label{f:StrSemanticCompare} 103 \end{figure} 104 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. 142 TODO: finish the fast-copy case. 143 Java strings lacking mutation means that aliasing is not possible with the @String@ type. 144 Java's @StringBuffer@ provides aliasing, though without supporting symmetric treatment of a fragment referent; as a result, @StringBuffer@ scores as \CC. 145 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 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). 157 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 scolled or zoomed to overlapping, but potentially different, ranges. 159 160 The remainder of this chapter explains how the \CFA string achieves this usage style. 161 40 162 41 163
Note: See TracChangeset
for help on using the changeset viewer.
