This paper informally presents the algebra, shows that it is sufficient to define search functions, and then contrasts it with other models of substring values. Later sections of the paper contrast various models of substring values, show how the subsequence algebra can be concisely implemented, and touch on the many other aspects and advantages of the algebra. Examples are given in Ness, a language incorporating the algebra which is implemented as part of the Andrew Toolkit.
Keywords: strings, substrings, sequences, programming language design, applicative programming, string searching, rich text, document processing, desktop publishing, Andrew Toolkit, ATK, Ness
Despite the importance of text and strings, programming languages have offered no innovations in string data types or operations since the introduction of pattern matching and substr which happened at least as early as COMIT [Yngve, 1963] and PL/I [IBM, 1965], respectively. The most recent innovations, in Icon [Griswold, 1983], retain the standard string data types and augment them with carefully designed control structures.
This paper defines and demonstrates a new data type for strings by introducing a subsequence algebra and specializing it to strings. In the algebra each value is a reference to a subsequence of a base sequence, so each single string value represents an entire substring. With other string models multiple variables are required to represent a substring, leading to more complexity and errors. Please note that although this paper discusses an algebra, the presentation is informal and not algebraic. See [Hansen, 1989a] for a formal definition.
That there is a need for a new string data type is a consequence of three emerging trends:
Desktop publishing is accustomizing users to text with typographic formatting, multiple character sets, and even embedded objects: rasters, drawings, equations, footnotes, references, and so on. Such text can be dealt with in existing programming languages by the addition of various library packages and augmentation of the compiler and runtime system to accept non-ASCII characters in string values. However, since much effort is required to make these enhancements it is appropriate to introduce a new data type at the same time.
Applicative programming can be characterized as programming without side effects; an expression as written can be examined purely for its value so the reader need not keep the many details of possible side-effects in mind. The psychological advantages of this approach have not been explored in depth, but are related to the notions of modularity reviewed in section 3.4.2 of [Shneiderman, 1980]. As section 4 will show, traditional string value architectures encourage the use of side effects, at least to the extent of requiring two separate statements to record the position of a substring in one variable and its length in another.
"Professional non-programmers" denote professionals who are not programmers, but who happen to program computers as a tool in their work. Recent interactive systems such as Hypercard [Atkinson, 1987] have introduced programming languages intended for these people. While it is true that these languages do not permit control over every CPU cycle, they compensate by allowing clear and concise programs.
To satisfy these three emerging trends, the string facility of a language should be something that can be described as follows.
Simple. Programs are short and straightforward. A minimal
number of data types and concepts are required to read and write programs.
First Class. Strings and substrings are as well supported as
numeric values. Syntactic forms are offered for concatenation, string
constants, and declaration of substring variables. Semantically, substring
values can be passed as arguments to functions and returned as values.
Comparison and assignment apply to substrings.
Unbounded. String values are not declared with size bounds
and string expressions have no such bounds. The implementation manages
the space for all strings.
No widely used programming languages combine all four characteristics. Most lack Simplicity and First Class substrings, as will be discussed in Section 4. A few language provide Unbounded string values; for instance Icon, LISP [Steele, 1984], Awk [Aho, 1979], and REXX [IBM, 1987]. The latest version of C [ANSI, 1990] has reached toward Rich strings to the extent of offering a data type for "wide" characters and library functions for conversions between wide and multi-byte representations. Despite this added complexity, C cannot be said to support typographic styles or embedded objects. That no language currently offers Rich strings is not surprising given how recently desktop publishing has become practical. Most languages with First Class strings could be extended to provide Rich strings as well by redefining the syntax of string constants, providing a suitable implementation and defining functions to operate on typography and embedded objects.
The only two languages satisfying all four criteria, Ness [Hansen, 1989b; Hansen, 1990] and cT [CDEC, 1989], both base their string data type on the subsequence algebra presented here. Both were originally implemented under the Andrew Toolkit (ATK) [Morris, 1986; Palay, 1988], although cT has recently been re-implemented. The capability range of ATK is illustrated by this paper: a single file with various embedded objects created using ATK's ez text editor. Examples below are given in Ness, the full power of which can be noted from the fact that under 2600 lines of Ness code are needed for a translator to ATK format from Microsoft's Rich Text Format (RTF) [Microsoft, 1990]. Typographic styling is permitted in Ness programs; the programs below were compiled and executed without removing the styles.
In this paper, the subsequence algebra is introduced in the first section
followed by descriptions of non-primitive and searching functions in
the next two sections. The fourth section contrasts the algebra with
alternative models of strings. The comparison is continued in the
fifth section with an in-depth examination of solutions to a practical
problem. The sixth section discusses implementation showing that the
algebra cannot be comfortably implemented as a subroutine package but
can be readily compiled. Many additional aspects of the algebra are
summarized briefly in the seventh section.
A subsequence reference algebra is a four-tuple [E, S, R, O] where E is a arbitrary set of elements and O a set of operations defined over a domain R derived from the set S of sequences over E. Specifically we define these terms:
Each element of R is a triple [b, l, r] where b is a sequence in S and l and r are positions in b.
An element of R is called a subsequence reference, or
subseq. A subseq [b, l, r] is said to
refer to the elements of b between the two positions
l and r. If l and r are the same, the
subseq is said to be empty.
For discourse, the elements in a sequence are imagined to be in a horizontal line with earlier elements to the "left" of later elements. Note that empty sequences are not all equivalent; they may differ as to their locations within their bases. Usually the operators O will include a nullary operator for constants which maps the denotation of a sequence of elements into a subseq with that sequence as a base and positions at its opposite ends. Other operators map subseqs to subseqs.
When a subsequence algebra is incorporated as a data type in a programming language, there is no need for values which are elements of E or S since both can be represented by elements of R. For a single element from E, the subseq in R has a base string containing the element and the two positions on each side of it. For a sequence from S, the subseq in R has that sequence as its base and the two positions at opposite ends.
For common programming languages the specialization of a subsequence reference algebra would define the set E as set of ASCII characters. Several languages implement the operator set O with mixed domain functions like substr(r, i, j) where the first argument is a string and the others are integers. Usually however, the resulting reference is to a new base sequence rather than the original r. The specialization in this paper employs a richer set of elements, a set of operations defined solely over the domain of substrings, and result values that refer to the base strings of their arguments.
When the elements referred to by a subseq are characters it will be common below to talk of it as a substring. Figure 1 shows three substring or subseq values, m, s, and p, defined on the base sequence "'Twas brillig and the slithy toves" and referring respectively to "s bril", an empty subsequence, and toves.
In the rest of this paper we specialize to "the" subsequence algebra
[E*, S*, R*, O*] where:
is Japanese for Do you play go?"
In the Figure, start(m) is the empty subseq between a and s; and the values of base(m), base(p), and base(s) are each the entire sequence between < and >. To get an empty subseq at the beginning of x's base sequence, we can write start(base(x)). The opposite composition, base(start(x)), returns exactly the same value as base(x) because x and start(x) are both on the same base sequence.
Given two subseqs x and y, it is possible to determine whether both are on the same base sequence as long as both are not on empty bases. They are on the same base if (base(x) = base(y) and extent(base(x), base(y)) = base(x)).
In terms of Figure 2, m ~ p is a subseq whose base is the new value "s briltoves" and whose positions are at the extremes of that base.
In examples below, subseq variables are declared with the form:
Function arguments and values are subseq values by default. Assignment of subseq values does not copy the string referenced; instead it copies only the reference. Comparison, however, compares the strings referenced and does not distinguish between strings on different bases. (In the Ness and cT implementations of the algebra, the declarator is "marker" instead of "subseq.")
Given a subseq value we can write simple operations to scan through the base string. If m refers to a blank, we can advance it to point to the nearest following non-blank with:
Note that this loop will terminate with m referring to either a non-blank or to the empty subseq at the end of the base. Of course, if m originally referred to a non-blank, it would remain unchanged. Denoting the initial value of m as m0, the loop invariant before the predicate is that extent(m0, start(m)) is all blanks.
Suppose m refers to a word, that is, consecutive non-blank characters with adjacent blanks on both ends. To find the next word we must first skip the blanks following m and then build a subseq referring to everything prior to the next blank. In the Ness implementation of the algebra, this is written as:
The first while loop scans across all blanks after m and the second scans across all subsequent non-blanks to accumulate the word. The test next(m) /= "" checks to see if m ends at the end of its base, in which case it is deemed to be at the end of a word. When there is no word, nextword returns an empty string. For a shorter version of this function see Section 3.
Even this brief example can illustrate how values in the algebra are First Class and aid in applicative programming: the result of one function can be directly passed as an argument to another. For instance the statement
will pass to addToTable the entire word returned from nextword. No global variables or side effects are required; the computation within nextword or addToTable can be arbitrarily complex and the same functions can be utilized in other contexts. As sections 4 and 5 will discuss, coding this statement is more awkward with other popular models of string values.
The operators start and next are asymmetric with
respect to text order in that one moves from left-to-right and the
other returns the leftmost position in its argument, while the corresponding
operators for the reverse direction are non-primitive. This asymmetry
reflects a decision to engineer the primitives for the most common
order of examining text. Indeed, in some implementations utilizing
multi-byte character encoding there may be a performance penalty for
right-to-left traversal.
| Function | Definition | Expression |
| finish(x)
| the empty string at the point where x ends
| start(next(x)) |
| front(x)
| the element which starts where x starts (even if x is empty) | next(start(x)) |
| rest(x) | all of x past its first element (empty if x is empty) | extent(next(front(x)), x) |
| first(x) | first element of x, but empty if x is empty
| extent(x, start(rest(x))) |
| last(x) | the last element in x, or x itself, if it has no elements | {see text} |
| previous(x) | the element preceding x | last(extent(base(x), start(x))) |
Finish is analogous to start and also produces an empty subseq, but at the other end of its argument. Functions front, first, last, and previous all produce subseqs for single elements analogously with next. Rest(x) returns a subseq one element shorter than x.
Figure 4 illustrates further the non-primitive functions of Table 1. Here variable m has the same properties as q in Figure 3 and variables s and p show the results for empty and one element values, respectively. First and front differ in their values only for the empty subseq s; in this case, first(s) is s itself and front(s) is the element next(s). Note that for s and p the functions first and last both return their arguments as their values
The expressions for rest and first exploit the definition of extent. When x has one or more elements, the value of next(front(x)) begins just after the first element, so the expression for rest produces a value extending from just after that first element to the end of x. When x is empty, its end precedes the start of next(front(x)), so the result for rest is the empty subsequence at the end of x, which is the same value as x itself, as per the definition of rest. The same trick applies in the definition of first, which gives the single element preceding rest(x) if x is non-empty, but otherwise x itself.
One way to implement last(x) is with a loop examining each of the subseqs
looking for one, say t, for which extent(finish(t), finish(x)) yields the empty string. Then t is the desired last element. A more elegant recursive definition relies on rest:
The then case applies when x is initially empty or when the recursion has descended to the last element; otherwise the else case recurs to compute the last element in the rest of x, which will be the same as the last element of x. In practice, of course, last is implemented about the same way as next.
For more insight into the algebra, the reader is invited to define functions of subseq m which produce the second element of m or the subsequence from the beginning of m to the end of its base. It is also amusing to find the middle of m without doing arithmetic. With the latter as a function named middle, there is a simple solution to one typical formal language theory problem: the expression
has the value True when the two halves of s are identical.
The search operations below each have two arguments, a subject and a specification. By convention in Ness, the subject both bounds the range in which the search is conducted and specifies the value returned if no satisfactory substring is found. If the subject argument is non-empty, the range is that substring; but if empty, the range extends from the location of the subject argument to the end of its base. Since a successful search always yields a non-empty substring, failure is indicated by returning an empty string, usually the one at the end of the subject argument. These conventions are related since the end of the subject argument appears in both. Although this relationship has not proven awkward in the many programs written so far, there is certainly room for argument as to exactly what conventions are best.
In the descriptions below, when the second argument--the specification--is obj, the match must be an exact match, character-for-character; but when it is set, the string is treated as a set of characters. A typical set value is "0123456789" for the set of all digits. These functions are illustrated in Figure 5.
Utilizing the search operations we can now rewrite nextword of Section 1 more briefly as
Of course, if we had a variable wordCharacters giving a complete set of characters allowed in words, nextword would be simply
This latter approach suffices for English or the European languages, but perhaps not for the universe of all letters of all languages.
The search functions can be defined entirely in terms of the primitive operations of the algebra. We begin with a simple support function which searches a string src looking for a single character c. If found, a subseq for it is returned, otherwise the function returns an empty subseq at the end of subj:
This function illustrates one form of loop; at each cycle around the while loop, src is one character shorter by virtue of the call on rest(src). The loop ends if either src becomes empty or its first character matches c. If c should happen to be empty, this version of findchar will also return an empty subseq, although not without first searching all of src. The loop invariant before the predicate is that c is not equal to any character in extent(src0, start(src)), where src0 denotes the initial value of src.
Algorithm 1 expresses span as a function in terms of findchar and the primitive operations. The first if-then sets s to be the range of the search as defined by the search conventions: if subj is non-empty, the search is limited to its length, but if empty the search extends from the beginning of subj to the end of the base, as computed by extent(s, base(s)). The loop has the same paradigm as the one in findchar, calling rest(s) at each step to shorten s by one element.
Sometimes a loop advances through a string in steps longer than one character at a time, as illustrated by the search function in Algorithm 2. Each cycle of the while loop calls findchar to find the first character of obj and then calls match to determine if all of obj has been found. If so the appropriate value is returned, but if not, there is no point to re-checking extent(s, f), so s is set to everything after f. If s becomes empty, findchar returns an empty subseq and the loop exits via the test of f = "" .
In the Ness implementation of the subsequence algebra, search is coded with a far faster non-linear search [Sunday, 1990]. The details of match, token, and trim are left as exercises to the reader.
One common programming technique in Ness--which has neither arrays nor structures--is to store data tables in strings and look up values in them with search. The result of the search is a position in the table and associated data can be found at adjacent locations. Algorithm 3 utilizes this technique to scan a text and replace names of games with icons. A sample execution might convert
to
is older and more interesting
than
and
.Note that the program builds the result by concatenating strings.
checkers:
Go:
"
function IconifyNames(text)
At each step in the loop the token operation gets a reference to the next word and then characters preceding it are concatenated with the result. If no word was found, word will be the empty subseq at the end of text, so the result is complete and can be returned. The call on search determines if the word is in the GameNames table and, if not, returns an empty at the end of the table so that next will also return an empty value. The final if-then-else inserts either the icon or the word into the result. Note that a space and colon are appended to word as the second argument of search; this prevents partial word matches so, for instance, check will not be converted to its following character, e.
Unitary. In the Unitary model of strings, also sometimes called the "free monoid over the character set," each string value is a distinct, atomic object. Operations and string functions return values that are effectively new strings with no relation to other existing strings. Unitary strings can certainly be First Class, given the right implementation, however, they are not always Simple to use. Problems arise for parsing and searching operations because the result of a search must report not only the string which matched, but also its position. For instance, it may be desirable to test adjacent punctuation.
Although there are no major languages with a pure Unitary model of strings, the possibility has been demonstrated by Eli [Glickstein, 1990]. In this Lisp-like language, search functions return a list of three strings which could be concatenated to recreate the original subject string. The middle element of the list satisfies the search specification and the other elements are (copies of) the preceding and following portions of the subject.
Starting at least as early as XPL [McKeeman, 1970], implementations of Unitary string values have not actually copied strings to produce new values. Instead each new substring value is produced by creating a reference to it within its base. Although this is much like the values posited in the subsequence algebra, these languages do not expose this machinery, so it is impossible to define the primitives next, base, and extent.
Positional. In the Positional model, a string value is a pointer to a string or an integer index to an element of a string (usually the latter is in the Unitary model). Such values can easily be First Class since integers and pointers are themselves First Class, but the Positional model is not quite so Simple. Complexity is increased if there are both positions and unitary values; it is also increased by having recourse to a domain--integers or pointers--outside the domain of strings. Simplicity suffers also because a position by itself cannot select a substring without conjoining a length or another position. These extra values entail extra variables and more assignments, thus increasing program size and decreasing its comprehensibility. Confusion is compounded by the potential for off-by one errors: does a position value refer to an element or the gap between elements? With integer positions, is the first zero or one?
The quintessential example of the Positional model with pointers is C, wherein a string value is a pointer to a string or a tail of a string. To illustrate the awkwardness of returning substrings in the positional model, consider the function token which finds a substring and returns a reference to it. The function must be defined with an additional argument pointing to where to store the length:
If token(x, &n) is evaluated, the substring it locates cannot be directly passed as an argument to another function as in
because the value of n passed to g would not necessarily be the value assigned by token to *len. To be correct, the computation needs two steps
Such extra steps and variables can increase the opportunity for error in a large program.
Integer positions are found in many languages, including PL/I and Fortran [ANSI, 1978]. Pointer and integer positions are not entirely equivalent. If a string is copied, integer values referring to positions in the original will refer to the same positions in both copy and original. With pointers, pointer arithmetic is needed to compute from a pointer into the original a corresponding pointer into the copy.
Overlays. There are a few languages, like Lisp, PostScript [Adobe, 1985], and even COBOL [ANSI, 1985], which permit one string to be defined as an overlay on top of another, thus making the defined string a subsequence reference. None of these languages, however, offer functions sufficient to enable implementation of next, base, or extent; the overlaid string behaves as though it were itself a Unitary value.
APL algorithms sometimes employ a very general form of substring; the algorithm associates a bit vector with a base string and the one bits in the vector select elements of the string to be in the substring. For instance, this expression
( b 
9 \ b , t =
'''' ) / t
removes from t all substrings quoted with paired
apostrophes [Bernecky, 1991]. Execution begins with the subexpression
b , t = ''''
which assigns to b a bit vector with ones in the positions
of the apostrophes, the 9\ converts to a vector for the
characters inside the apostrophes, and finally 
computes a vector indicating the positions of characters to be retained
in the result, which is produced by the final /t.
Bit vectors are a very general tool since they can select non-contiguous
subsets of the characters in a string; however, to pass arguments to
general functions both the bit vector and the base string have to be
passed. Moreover, functions cannot return both a string and a bit
vector as a single value.
Icon. To reduce program size and the need for extra variables, Icon provides a special operator, ?, for pattern scanning. The expression
first makes string value s be the value of the global variable &subject and then executes the operations. The current position in the subject is given by another global variable, &pos, which initially has the value which indicates the position before the first character. String operations upto, many, find, any, match, and bal examine &subject starting at &pos and return a new position, depending on their nature. Two other functions, tab and move, change the value of &pos and return the string portion between the old and new values of &pos. Thus it is common to write statements like
which advances &pos across a sequence of letters and assigns to t a copy of the string value passed over, in this case the next sequence composed entirely of characters from the set letters. Since functions like many may not find any instances of the set, the concept of failure is employed in Icon. If no values are found, the expression "fails," which initiates backtracking or, if that is not possible, terminates the scanning operation and all other operations on the stack up to a conditional statement.
Not only does Icon have the additional complexity of offering both the Unitary and Positional models, but there are separate sets of functions for each. There is a potential for confusion between tab and move, the Unitary model functions, and many, upto, and the other Positional model functions. Indeed, it would be interesting to know if omission of required tab and move operations is a common error in Icon programs.
Subsequence references incorporate both a string value and the position of that value within its base. Thus it is a First Class value for substrings suitable to return from parsing or other searching/scanning operations. It is common in programs written with the subsequence algebra to utilize a single variable both for its value and its position: In Algorithm 1, variable s is utilized for its first character with first(s), its position with start(s), and its extent with rest(s). In Algorithm 2, the results of findchar and match are stored in f and m respectively. Since both are on the same base as s, the new value of s can be set to begin after f and the value of m can be returned, both retaining the position in the original base string. In Algorithm 3, the variable word appears both for its value and its position in its base. In all these cases more variables and assignment statements would be required with other string models.
Although internally more complex than integers, subsequence references are Simple in that they reduce the required number of concepts, even beyond the fact that the single concept obviates the need for both Positional and Unitary values. With a subsequence reference model of strings, neither character nor string values are required, as shown in the beginning of Section 1. Moreover, instead of requiring the semantics of multiple domains, subsequence references require only those described in Section 1. This can be valuable when presenting string processing to users who are uncomfortable with numbers.
where <WS> is whitespace, <key> is one of five words, and <text> is arbitrary text. When <key> is if, ifdef, or ifndef the output is
but when <key> is else or endif the output when <text> is non-empty is
and when <text> is empty is
If the input line does not have one of the expected forms, it is returned unchanged.
Subsequence Algebra and Ness
In the subsequence algebra, as instantiated in Ness, the problem can be coded as in Algorithm 4. Note that keytable is defined in 4a with a "long constant" construct delimited by // and \\. The text between the delimiters is the exact constant, newlines and all. If there were tabs, other control characters, and escape sequences, they too would remain untranslated. This form of constant is a valuable addition to the syntax of string languages because it allows the programmer to encode strings exactly as they are to appear. In addition to keytable, 4a defines whitespace and letters, which are later used as arguments to span and trim. The function skipwhite defines a particular scanning function suited to the problem; it could easily be written in a language with a Positional model since it effectively returns the position following any whitespace after its argument. The other function, nextfield, is an excellent illustration of subsequence references; its argument is a reference to a semi-colon-delimited field in keytable and it returns the following such field.
NormalizeLine itself, in Algorithm 4b, utilizes variable
t as the current position in the line. The algorithm begins
by skipping whitespace, checking for a "#", and skipping more
whitespace. Next, t is set to <key> by spanning subsequent
letters and <key> is sought in keytable with the result
being assigned to fix. The last assignment to t
gives it a value extending from the first non-whitespace character
after <key> to the last non-whitespace character on the line.
This value together with the fields following fix are used
to build the final result value.
The usage of nextfield
in Algorithm 4b deserves emphasis. Since its value is an entire field,
that value is suitable for concatenation to construct the result as
in the final return
statement. But since its value is a subsequence reference, it can
also serve as argument to a function (in this case, itself) to locate
and return the next following field, as in nextfield(nextfield(fix)).
The reader is invited to try to code this expression in other languages.
C
The C programming language is very close to hardware level, as befits a language intended for writing a compiler and operating system. String constants are provided, but all other string operations are deferred to library functions. The usual C paradigm is to perform string operations with in-line loops. For instance, to skip across whitespace the code might be:
while (isspace(*t)) t++;
The need for these loops is reduced with functions like strspn, but they still occur as in the loop to trim the text.
The C version of NormalizeLine in Algorithm 5 begins by skipping whitespace, checking for a "#" and skipping more whitespace. The next lines set key and t to opposite ends of the key and then search for the key in keytable. Subsequent lines find the <text> by skipping whitespace after the key and then scanning backward to find the last non-space character. The last section of the algorithm builds the output by copying the prefix from the table, the text from the input, and the postfix from the table.
It may be obvious to the reader that textlen can be negative, but was not so to the author. Consequently, this was the only one of the versions that had a bug beyond syntax errors. This sort of error is more common in Positional model programs because there are more variables to keep in mind while coding.
In the actual C program from which the problem was taken, NormalizeLine
modified its argument rather than returning a copy. This requirement
is crucial because without it, as in the Algorithm, the program is
seriously flawed: The first three return statements return the initial
value of line, the fourth returns a pointer to a constant,
and the last returns newly allocated memory. Since the calling routine
cannot effectively distinguish the storage class of the result, it
cannot deallocate the allocated memory and the program will consume
memory proportional to the input. This problem of managing storage
is one of the chief defects of C for string processing.
Icon
Icon is a large language featuring many innovative constructs beyond those of Ness and C, so two versions of NormalizeLine are presented, one utilizing a subset and the other the full language. The subset is limited to approximately the control constructs and data structures which are available in Ness and is utilized in Algorithm 6. Here the function many(cset, string, i) scans string starting at position i and returns the position of the first charactrer encountered which is not in cset; if none is found, it fails. Subscript expressions of the form [i:j] select the substring extending between positions i and j. The find operator not only returns the location of the beginning of what it finds, but also succeeds or fails. Thus it is essential in the Algorithm that the first assignment to tblloc be inside the if predicate to determine whether key was found. In the next line the expression t+*key computes the position after the key as the starting point for skipping more whitespace. In constructing the result value, fieldend computes the end of fields whose beginnings must then be held in other variables; in this case tblloc and postloc.
The full Icon language is exploited by Algorithm 7, which employs the string scanning operator ? described in Section 4. Each of the calls on tab or the = operator advance &pos so it serves as the start for subsequent operations. The '| &pos' clauses provide a default value for tab in case the many function fails to find any of the characters it is looking for. The \keytable[...] expression searches the keytable for the key; if found, fix is set to the record found, but otherwise keytable has the value null which is converted by the backslash operator into a failure which propagates out to the if (after some futile backtracking).
Comparison
Cursory examination shows the Ness and full Icon versions of NormalizeLine in Algorithms 4b and 7b to be briefer than the others, to use fewer variables, and to avoid explicit recourse to arithmetic. The flow of the logic matches the number of statements, without extra assignments to save separately the two opposite ends of substrings. For more detailed comparison we can consider the algorithms to have four phases: skip hash and white space, find and process <key>, isolate <text>, and build output. The first phase is roughly comparable in all the languages since it is simply a matter of moving a position past unwanted material, but the other phases differ considerably.
In the <key> phase, the Ness version utilizes a single variable, t, to represent the key, whereas C and the subset Icon code each need two (key and t for C; t and *key for subset Icon). The string scanning operation hides this in the full Icon version: tab(many(&lcase)) advances &pos across the key and returns a copy of its string value.
For the <text> phase, the Ness and subset Icon versions both set a single variable to the text. The C code is more complex only because the trim function is performed explicitly with a loop. The full Icon code illustrates Icon's potential for convoluted code: the function name trim is considerably separated from its arguments, tab(0) and whitespace++'\n'; and surrounding these is an if statement semantically linked to the = and \ operators inside trim's first argument.
In the final output phase, the Ness and full Icon versions simply concatenate
the appropriate values. The other two versions illustrate the deficiencies
of the Positional Model by requiring several variables to keep track
of the ends of the pieces to be concatenated.
The four versions of NormalizeLine reflect markedly different programming languages. We can say qualitatively that Ness is wordy and uses few concepts, C is low level, and Icon achieves brevity through special operator characters and a variety of data structures. These notions can be informally quantified by counting the number of operator instances, as shown in Table 2. The operators counted are listed in the body of Table 3.
| # unique operators | ||||
| # operators | words | symbols | # concepts | |
| Ness | 49 | 11 | 4 | 6 |
| C | 74 | 12 | 13 | 12 |
| Icon subset | 58 | 8 | 9 | 10 |
| Full Icon | 49 | 7 | 10 | 14 |
In Table 2 we see that C uses the most operators, subset Icon fewer, and Ness and full Icon the least. Note, however, that Ness uses sixteen fewer operations to initialize keytable and nine more to extract fields from it; for this example the Icon language could benefit from constants for table initialization and Ness could benefit from some form of table construct. From the relative use of words versus symbols for operators, it is apparent that Ness de-emphasizes syntax, despite the disadvantage of longer program texts. With infix operators for the primitives and shorter function names, the Ness definition of the body of NormalizeLine would be about the same size as the full Icon version.
Concept
Ness
C
Subset Icon
Icon
assignment
:=
= += ++ --
:=
:=
function call
return
return
return
return
condition
= /=
!= ! <= == &&
strncmp isspace
strspn
== ~== not
==
if
if
if
if
if
string references
~ next start
extent finish
nextfield
search conventions
span search
skipwhite trim
strncmp strspn
find many trim
upto fieldend
many trim
loops
while break for
arithmetic
+ - += ++ --
+ -
string values
|| [
tab ||
string positions
* strspn strlen
strncpy strnput
strncmp
* find many
trim upto
fieldend
many trim tab
pointer
*
memory
malloc
character sets
isspace
++
++ many
record
->
affixes .
failure
if not
if many | = \ ==
generator
|
alternation
|
string scanning
? =
table
table [
The real difference in complexity can be seen by counting the "concepts" required to understand each version. One way to do this is to classify each operator according to what concepts it employs, as shown in Table 3. Clearly the reader can argue with at least one of the assignments of operator to concept, but it seems clear that the Icon versions use about twice as many concepts as the Ness version. There are two ways to consider this: if language complexity is to be minimized, Icon is far more complex; but if complexity is acceptable, the subsequence algebra can be incorporated in a complex language permitting NormalizeLine to be expressed even more succinctly. With the algebra, the extra complexity of additional data types is not required in order to attain short programs.
The biggest problem is management of string storage: to conserve space, a base sequence can and should be deleted when no subseq refers to it. In a low-level language like C which does not provide storage management, the string manager must keep track of all subseqs to manage their space and that of the base sequences. This may be impossible, however. Consider expressions where a string value returned from one function is passed as argument to another as in this fragment from Algorithm 4:
Skipwhite allocates a subseq and returns either it or a pointer to it. But then, which routine deallocates that memory and when? The simplest option is to never free the memory occupied with subseqs and base sequences, but this profligacy may lead to excessive paging or program termination. Subseqs and base strings constitute a non-circular structure and can be managed with references counts instead of more general and costly tools. However, if the algebra is implemented in a higher level language with storage reorganization, the more general tools are likely to be used--with consequent excess cost.
When successfully implemented as a package, the algebra must be defined in terms of some more primitive notion of strings provided in the language itself. This means two separate string mechanisms with an attendant loss in efficiency and increase in the number of concepts a program reader may encounter.
Finally, a string facility requires lexical support for string constants and a primitive operation--preferably syntactic--for concatenation. Few languages are flexible enough to be extended in these directions. Moreover, if strings are to support typographic styles and embedded objects there is the further requirement that the program development support system also support editing of programs containing such constants. Thus program editing must move closer to word processing and programs can begin to have typographic styles themselves.
Given the deficiencies of a library implementation, it is reasonable to assume that we are implementing the subsequence algebra as the native tool for strings in a high level programming language. Although this paper has claimed no interest in efficiency, it turns out that the subsequence algebra can be implemented without undue overhead. Should the algebra become widely used, appropriate compiler optimizations will ensure acceptable execution speed. With even wider use, computer hardware will adapt to the algebra as it has for floating point and programming languages, as in [Hester, 1990].
Central to an implementation are data structure definitions for subseq values and base strings. Additional data structures are needed for typographic styles and embedded objects, to whatever extent they are supported by the implementation. The Ness implementation of the algebra relies on the Andrew ToolKit (ATK) implementations of these data structures, so the language development entailed little new data structure design.
In ATK, base strings are stored as a physical sequence of characters in a space larger than the string itself. The unused space is retained as a gap within the base at the position of the most recent modification (since ATK and Ness allow modification of base sequences). If consecutive modifications tend to happen at nearby locations, the overhead of copying characters to make changes is imperceptible [Hansen, 1987].
One alternative to physically sequential storage is a list of characters. Insertions and deletions are far faster, but space requirements mushroom and performance degrades with increased paging as the list gets fragmented among many pages. Experience has demonstrated that sequential text storage reduces paging sufficiently to offset the cost of copying strings when changes are made. Of course there are numerous intermediate data structure designs with linked lists of elements each having a physically sequential block of text. We have not tried this approach because the physically sequential approach has been satisfactory.
The minimal implementation of an immutable subseq is three words: a pointer to the base, and representations of the leftmost and rightmost positions. When the elements are stored consecutively, integers suffice to indicate positions, so a subseq value can be described in C as:
A fourth word is required if the implementation chooses to implement "reference counting" by linking together all subseqs on each base. The algorithms below assume that a struct basestring has at least got fields l and r to indicate the two positions at its ends.
Operations in the algebra are most succinctly implemented by modifying their argument, so, in an applicative environment, the code compiled to pass a subseq as an argument copies its value to the stack. Suppose these stack elements are struct subseqs as above with x pointing to the first argument on the stack and y to the second. Then the four primitive functions can be compiled as if they were:
In two places integer comparison determines the ordering of positions; this would have to be changed if base strings were not stored consecutively. Similarly, the ++ in next must be modified if elements occupy more than one byte. Conceptually, these are the only places in the implementation that require knowledge of the implementation of base sequences.
For a simple assignment like
the stack is inefficient. An optimizing compiler could copy s
into m and then set m->r= m->l. If we are compiling for the
IBM RISC architecture, the entire statement could take as few as three
instructions: a load-multiple and a store-multiple to transfer the
subseq representation and an additional store to m->r. For assignment
of an expression with more operators, the overhead of copying the initial
value is distributed among them all and is thus proportionately lower,
so the average number of instructions per primitive is low.
Invariants. In writing invariants, it is often desirable to express attributes of subsequences. As shown in various of the examples above, invariants can be succinctly expressed in the subsequence algebra.
Integer positions. While the algebra permits ignorance of a Positional model of strings, it does not preclude it. For instance, the primitives are sufficient to implement nextn(s, n) as the result of applying next a total of n times starting with the initial value s. Then the traditional function substr(s, i, j)--which returns the substring of s starting with the i'th character and extending for j characters--is
By defining substr in terms of next, there is no question that the indices refer to elements rather than byte positions in an array.
Arrays. With nextn and a simple trick, sequences can subsume one-dimensional arrays. The trick is to address the array by a reference to the empty element at its start. Thus if A is an array, nextn(A, i) returns the i'th element of the array. A compiler could optimize such applications so the user could deal with arrays without the introduction of special syntax or the complexity of understanding a new data organization.
Formatted text. In addition to permitting text with arbitrarily styled segments, it is valuable to have operators to manipulate styles. These operations are convenient to define with the subsequence algebra because a style naturally applies to a subsequence of the text. In the Ness implementation, functions are provided to add styles, remove them, interrogate the style of text, and traverse the text in sections delimited by style change boundaries.
Embedded Objects. When sequences permit embedded objects the language needs operations to convert an object into an element of a sequence and to extract an object from a sequence. It is also useful to be able to interrogate an element to see if it is an object, and determine its type.
Multi-media. This term sometimes means just voice and video, but is more generally applicable to text or applications with embedded objects of all sorts. A voice recording, video clip, or other multi-media component can be incorporated in a document as a single embedded object and manipulated with the object operators of the preceding paragraph. An exciting possibility is to represent the time sequence of the voice or video object as a subseq. Arbitrary reference to and rearrangement of such sequences would then be possible under program control.
Mutability. Much literature has been devoted to applicative versus imperative programming. The subsequence algebra has been presented in a purely applicative form above, but a sequence modification operator can easily be defined (and not quite so easily implemented). Replace(s, r) modifies the base sequence of s so the portion that was referred to by s contains a copy of r. In some applications--for instance text editors--where the base may have numerous subseqs referring to its parts, such modification can be a useful tool because the other subseqs remain attached to the base whereas if a new base were constructed it would have no subseqs on it. Replace is also useful when it can be employed to avoid creating new strings; the overhead of copying strings is not too bad, but the overhead of allocating memory and paging-in non-adjacent strings can be large.
General sequences. In an abstract view, there is little to choose between sequences and Lisp lists. The algebra can subsume lists if subseq values can be objects embedded in sequences. Of course, with this extension simple reference counting will no longer work and garbage collection will be necessary.
Unbounded sequences. The most general sequences are potentially infinite by virtue of being defined with a function to generate successive elements. The subsequence algebra is entirely adequate to deal with such sequences because only the next operator need access further along in the sequence--it would call the generator if necessary. The base operator would return a general sequence including a reference to the generator function.
all of which are closed over the domain of references to subsequences. This paper introduced these operations in the first section and showed in the second and third sections that these operators are sufficient to access other relevant substrings of a base string and to define various searching functions.
Also introduced in the Introduction were four characteristics that should be found in any substring data type; it should be Simple, First Class, Unbounded, and Rich.
That substring values with the algebra are First Class is evident from the definition; subsequence references are arguments and return values for the primitive functions; and other functions can share this property. That substring values are not First Class in other models of substring values is shown in Section 4.
Unbounded string values require automatic storage management as shown in section 6. Any language with storage management can have unbounded strings. But with the subsequence algebra, management of the string space can be more efficient.
Rich strings are supported by the algebra in that its abstraction
completely hides the physical representations of strings and sequences.
A substring reference is precisely the correct value to serve as an
argument to setting typographic styles or to return from a search for
text in a given style. Objects can be elements in base sequences,
and the description of an object can be a sequence itself.
Subsequence reference values raise many interesting practical issues, several of which are discussed in Section 7. Some of the most interesting are:
2. Semantics: Is there a better set of primitive operations? What are the best search conventions?
3. Implementation: What optimizations are possible and desirable in compiling subsequence expressions? What are the best data structures to support the algebra? Can modification of base sequences be implemented efficiently?
4. Generality: Can the subsequence algebra subsume arrays and list
processing, thus reducing further the number of programming concepts?
Can unbounded lists be handled satisfactorily with lazy evaluation?
Acknowledgments. Bruce Sherwood was a bountiful source of enthusiasm and encouragement; I am indebted to him, Judy Sherwood, David Andersen and others at the Center for Design of Educational Computing, Carnegie-Mellon University, who implemented and utilized the algebra as part of cT. This work began with the support of the Science and Engineering Research Council (Britain, grant number GR/D89028) and the Department of Computer Science at the University of Glasgow, under the stimulating direction of Malcolm Atkinson. Support for the Ness implementation in ATK was provided by the IBM Corporation and the Information Technology Center, Carnegie Mellon University under then director Alfred Z. Spector.
[Aho, 1979] Aho, A., B. W. Kernighan, P. Weinberger, Awk - A Pattern Scanning and Processing Language, Bell Telephone Laboratories, Murray Hill, New Jersey, 1979.
[ANSI, 1978] ANSI, American National Standard - Programming Language - FORTRAN, ANSI X3.9-1978, ANSI (NY, 1978).
[ANSI, 1985] ANSI, American National Standard for Information Systems - Programming Language - COBOL, ANSI X3.23-1985, ANSI (NY, 1985).
[ANSI, 1990] ANSI, American National Standard for Information Systems - Programming Language - C, ANSI X3.159-1989, ANSI (NY, 1990).
[Atkinson, 1987] Atkinson, B., HyperCard, Version 1.0.1, M0556 / 690-5181-A, Apple Computer (Cupertino, CA, 1987).
[Bernecky, 1991] Bernecky, R., "Fortran 90 Arrays," ACM SIGPLAN Not. 26, 2 (Feb, 1991) 83-98.
[CDEC, 1989] Center for Design of Educational Computing, CMU, The cTtm Programming Language, Falcon Software (Wentworth, NH, 1989).
[Glickstein, 1990] R. Glickstein, "Lisp Primitives in ELI, the Embedded Lisp Interpreter", available on X-windows distribution tape as .../contrib/andrew/overhead/eli/doc/procs.doc, Information Technology Center, Carnegie-Mellon Univ., 1990.
[Griswold, 1983] Griswold, R. E. and M. T. Griswold, The Icon Programming Language, Prentice-Hall (Englewood Cliffs, 1983).
[Hansen, 1987] Hansen, W. J., Data Structures in a Bit-Mapped Text-Editor, Byte (January, 1987), 183-190.
[Hansen, 1989a] Wilfred J. Hansen, "The Computational Power of an Algebra for Subsequences", CMU-ITC-083, Information Technology Center, Carnegie-Mellon Univ., 1989.
[Hansen, 1989b] Wilfred J. Hansen, "Ness Language Reference Manual", available on X-windows distribution tape as .../contrib/andrew/atk/ness/doc/nessman.d, Information Technology Center, Carnegie-Mellon Univ., 1989.
[Hansen, 1990] Hansen, Wilfred J., "Enhancing documents with embedded programs: How Ness extends insets in the Andrew ToolKit," Proceedings of 1990 International Conference on Computer Languages, March 12-15, 1990, New Orleans, IEEE Computer Society Press (Los Alamitos, CA, 1990), 23-32.
[Hester, 1990] Hester, P. D., "RISC System/6000 Hardware Background and Philosophies," IBM RISC System/6000 Technology, SA23-2619, IBM Corp., 1990, 2-7.
[IBM, 1965] IBM Corporation, PL/I Language Specifications, C28-6571-0, IBM Corp., Data Processing Division, (White Plains, NY, 1965).
[IBM, 1987] IBM Corporation, Common Programming Interface Procedures Language Reference, SC26-4358-0, IBM (Endicott, NY, 1987).
[McKeeman, 1970] McKeeman, W. M., J. J. Horning, and D. B. Wortman, A Compiler Generator, Prentice-Hall, Inc. (Englewood Cliffs, 1970).
[Microsoft, 1990] Microsoft Corp., Microsoft WORD for Windows and OS/2 Technical Reference, Microsoft Press, (Redmond, WA, 1990)
[Morris, 1986] Morris, J., M. Satyarayanan, M. H.Conner, J. H. Howard, D. S. H. Rosenthal, and F. D. Smith. "Andrew: A distributed Personal Computing Environment," Comm. ACM, V. 29, 3 (March, 1986), 184-201.
[Palay, 1988] Palay, A. J., W. J. Hansen, M. Sherman, M. Wadlow, T. Neuendorffer, Z. Stern, M. Bader. and T. Peters, "The Andrew Toolkit - An Overview", Proceedings of the USENIX Winter Conference, Dallas, (February, 1988), 9-21.
[Shneiderman, 1980] Shneiderman, B. Software Psychology: Human Factors in Computer and Information Systems, Winthrop Publishers (Cambridge, MA, 1980).
[Steele, 1984] Steele, G. L., Jr., Common Lisp: The Language, Digital Press (Bedford, MA, 1984).
[Sunday, 1990] Sunday, D. M., "A Very Fast Substring Search Algorithm," Comm. ACM 33, 8 (Aug, 1990) 132-142.
[Yngve, 1963] Yngve, V. H., "COMIT," Comm. ACM 6, 10 (Mar, 1963) 83-84.