\begindata{text,269832672} \textdsversion{12} \template{default} \define{italic menu:[Font,Italic] attr:[FontFace Italic Int Set]} \define{bold menu:[Font,Bold] attr:[FontFace Bold Int Set]} \define{chapter menu:[Title,Chapter] attr:[Justification LeftJustified Point 0] attr:[FontFace Bold Int Set] attr:[FontSize PreviousFontSize Point 4]} \define{section menu:[Title,Section] attr:[Justification LeftJustified Point 0] attr:[FontFace Bold Int Set] attr:[FontSize PreviousFontSize Point 2]} \define{subsection menu:[Title,Subsection] attr:[Justification LeftJustified Point 0] attr:[FontFace Bold Int Set]} \define{paragraph menu:[Title,Paragraph] attr:[Justification LeftJustified Point 0] attr:[FontFace Italic Int Set]} \define{bigger menu:[Font,Bigger] attr:[FontSize PreviousFontSize Point 2]} \define{indent menu:[Region,Indent] attr:[LeftMargin LeftMargin Inch 32768] attr:[RightMargin RightMargin Inch 32768]} \define{typewriter menu:[Font,Typewriter] attr:[FontFace FixedFace Int Set] attr:[FontFamily AndyType Int 0]} \define{display menu:[Region,Display] attr:[LeftMargin LeftMargin Inch 32768] attr:[RightMargin RightMargin Inch 32768] attr:[Justification LeftJustified Point 0]} \define{example menu:[Region,Example] attr:[LeftMargin LeftMargin Inch 32768] attr:[Justification LeftJustified Point 0] attr:[FontFace FixedFace Int Set] attr:[FontFamily AndyType Int 0]} \define{description menu:[Region,Description] attr:[LeftMargin LeftMargin Inch 32768] attr:[Indent LeftEdge Inch -32768]} \define{quotation menu:[Region,Quotation] attr:[LeftMargin LeftMargin Inch 32768] attr:[RightMargin RightMargin Inch 32768] attr:[FontFace Italic Int Set]} \define{subscript menu:[Font,Subscript] attr:[Script PreviousScriptMovement Point 2] attr:[FontSize PreviousFontSize Point -2]} \define{superscript menu:[Font,Superscript] attr:[Script PreviousScriptMovement Point -6] attr:[FontSize PreviousFontSize Point -2]} \define{smaller menu:[Font,Smaller] attr:[FontSize PreviousFontSize Point -2]} \define{heading menu:[Title,Heading] attr:[LeftMargin LeftMargin Inch -13107] attr:[Justification LeftJustified Point 0] attr:[FontFace Bold Int Set]} \define{majorheading menu:[Title,MajorHeading] attr:[Justification Centered Point 0] attr:[FontSize PreviousFontSize Point 4]} \define{formatnote menu:[Region,FormatNote] attr:[Flags PassThru Int Set]} \define{subheading menu:[Title,Subheading] attr:[Justification LeftJustified Point 0] attr:[FontFace Bold Int Set]} \define{center menu:[Justify,Center] attr:[Justification Centered Point 0]} \define{flushleft menu:[Justify,FlushLeft] attr:[Justification LeftJustified Point 0]} \define{flushright menu:[Justify,FlushRight] attr:[Justification RightJustified Point 0]} \define{leftindent menu:[Region,LeftIndent] attr:[LeftMargin LeftMargin Inch 32768]} \define{keyword menu:[Font,Keyword] attr:[FontFamily AndySans Int 0]} \define{ness menu:[Font,Ness] attr:[FontFamily AndySans Int 0]} \define{maths menu:[Symbols,Maths] attr:[FontFamily Maths Int 0]} \define{greek menu:[Symbols,Greek] attr:[FontFamily Greek Int 0]} \define{extra menu:[Symbols,Extra] attr:[FontFamily Extra Int 0]} \define{overstrike menu:[Symbols,Overstrike] attr:[FontFamily Overstrike Int 0]} \begindata{lookz, 269551176} hidden \enddata{lookz, 269551176} \view{lookzview,269551176,1,0,0} \majorheading{A Practical Algebra for Substring Expressions} \leftindent{\bigger{Wilfred J. Hansen*} Computing Science Department University of Glasgow \flushright{\smaller{May 1987}} ______________________________ \smaller{* Author's present address: Information Technology Center Carnegie-Mellon University Pittsburgh, PA 15213} ______________________________ } \indent{\bold{Abstract.} This paper introduces an algebra for sequences which has a number of desirable properties as a basis for string processing. In the algebra, string values are modeled as \italic{markers}, each of which represents a selected substring of some underlying base string. Six primitive functions on markers are described: next(), start(), extent(), base(), newbase(), and replace(). Together with appropriate definitions for comparison and assignment, these are shown to be sufficient for expressing all string functions and, moreover, conducive to the construction of readable, error-free programs. Examples are given in \ness{Ness}, a small language incorporating the algebra.} \formatnote{.bp} \heading{1. Introduction} An algebra is a set of functions closed over a domain of values. One algebra for strings is formed with the concatenation operator and the set of all strings over some alphabet. This algebra is fine for constructing strings, but is less useful for parsing: Suppose we search a string for "abc"; with the concatenation algebra alone, the result can be either "abc" or some other string to show failure. There would be no indication as to where the "abc" was found in the original string. The algebra described in this paper provides just such an indication. A "practical" algebra is one suited to provide a component of a programming language, for example the algebras of integer and Boolean values. To be practical an algebra must be \leftindent{\description{\formatnote{\\(bu} convenient -- simple operations should be stated simply; \formatnote{\\(bu }expressive -- all functions should be possible; \formatnote{\\(bu }consonant with the remainder of the language -- sharing a similar function call or operator syntax; \formatnote{\\(bu }representation independent -- the fact that some characters take more bytes than others should be invisible; and \formatnote{\\(bu }efficiently implementable -- no loops to implement fundamental operations. }} It should be based on a minimal core of functions which are sufficient to compute all values over which the algebra is defined. Practicality is not a formal property which can be proven; it is subjective and must be demonstrated by considering its applications. There are several problems with the algebras for string values implemented in major programming languages. Most assume that each character is represented by a single eight-bit byte, which does not provide a sufficient variety of characters for modern text processing. Many define a string as an array of characters, an organization which is prone to off-by-one errors with the use of integer subscripts. Others require reorganization of the entire structure of the language. Dissatisfied with the existing alternatives, we designed a new string processing facility based on the substring algebra presented below. In this algebra, string values are "markers", each of which refers to a substring of some underlying base string. Since the functions of the algebra are closed over substrings, there is no need for integer subscripts. Although the algebra is sufficiently general to describe algorithms over \italic{any} sequence of objects, this paper does not explore that aspect. The algebra has been implemented in a research language called \ness{Ness}, which will be used for examples [Hansen, 1987a]. The environment for this work is the Andrew system developed at Carnegie-Mellon University as a joint project with the IBM Corporation [Morris, 1986]. In conjunction with this effort, Carnegie-Mellon has been developing a version of the TUTOR language [Sherwood, 1977] used in the PLATO system [Alpert & Bitzer, 1970]. The new language is called CT [Sherwood and Sherwood, 1986]. This language is semi-interpretive with an operator-operands syntax similar to BASIC. The language has always provided extensive capabilities for generating graphics and analyzing student responses to questions, but has lacked string processing. The earliest programming languages had few or no capabilities for strings. Fortran could only print strings and the syntax was the notorious "Hollerith constant" which required the programmer to count the number of characters in the string: 3HUGH. Later versions of Fortran and other major languages like COBOL have generally treated strings as arrays of characters with all the limititations of arrays: storage must be allocated at the time of writing the program and characters must be selected with integer subscripts. One perrenial programming problem with integer subscripts is the question of whether the value refers to a character or the space between two characters; confusion over this point has led to numerous off-by-one errors. PL/I, although it treated strings as arrays of characters, did attempt to provide some amenities. It offered concatenation, but the result had to be assigned to a variable, and all variables had a maximum size. Parameters were call-by-reference, but if a string variable was passed to a function, there was no way of determining its maximum size. There was provision for selecting a substring, but the position and length of the substring had to be given as integers. A substring could be replaced, but only with another piece of text of exactly the same size. The XPL environment [McKeeman, 1970] may be the closest antecedent to the algebra presented here. String variables in that language refer to a substring of some other string. Each string expression produces another such substring value. The only string operations, however, are the integer based operations of INDEX and SUBSTR inherited from PL/I. Substrings could not be replaced; a new string value had to be created with concatenation. An unfortunate feature was that the implementation restricted strings to a maximum length of 255 characters, which is far too small for many applications. Even PostScript [Adobe, 1985], which has been designed specifically for complex typography, treats strings as arrays of characters which are accessed with integer subscripts. styles are not an attribute of a string but are described by the program containing the string. Strings are not variable-length encoded, boundless, or elastic. They are delimitable in that the search operator divides a string into three parts, but there is no other means of delimitation. SNOBOL [Farber, 1964] provided a language entirely oriented to string processing. Strings are so dominant that a portion of every statement is devoted to a pattern to be matched against a string. The mechanism for flow-of-control is supplanted by goto's based on "failure" to accomodate the fact that string pattern matching must return both the location of the match and an indication of success.* There is no way to refer to a substring so there is much copying of strings and there are even two forms of assignment which may be embedded in patterns. SNOBOL has many clever ways to shorten algorithms, but this results in a vast vocabulary that impedes learning the language. There is no set of fundamental concepts with which the language can be understood and to which the programmer has direct access. ______________________________ * "Failure" is an elegant control mechanism which should be considered for any language design. I did not use it in \ness{Ness} because I wanted to concentrate on the substring algebra and eliminate anything else superfluous or extraordinary. ______________________________ The recent language Icon [Griswold, 1979] has resolved many of these difficulties, but strings are still indexed with integers and provisions for pattern matching have still a large influence on the entire design of the language. None of the problems with the above languages is sufficient by itself to require a new approach, but a new problem has arisen: programs for bit-mapped workstations must process text in a far wider range of character representations. For efficiency it is still desirable to represent most characters with a single byte but some characters may require more. The complexities of text are such that they should be dealt with by system programming rather than as a part of every application program. Examining the problems with existing languages, we can say that a string processing tool should offer: \indent{ Convenience and Expressivity. The notation should easily express common string processing tasks and should fit comfortably within a traditional programming language. The programmer should not have to predeclare a finite length for the string and it should be possible to replace a portion of the string with a piece of a different length. Representation Independence. There should be no restriction on the size or representation of each character. Necessity and Sufficiency. The core of the notation should be a few simple functions which are sufficient for all string processing. Efficiency. Common characters should be represented in a single byte and there should not be unnecessary copying of string values. } In short, the algebra presented here did not arise as an abstract mathematical entity, but has been designed as a solution to human requirements. In that design process, when requirements conflicted the solution chosen usually was the one that best satisfied Convenience and Expressivity. The solution eventually reached was a notation based on the algebra presented below and implemented in an otherwise minimal language called \ness{Ness}. In addition to the functions of the algebra, \ness{Ness} offers marker declarations, assignment, if-then-else, while-do, predicates, compound statements, function definition, call (with call-by-value parameters), and return. Spare as it may be, \ness{Ness} was sufficient to write a preprocessor from itself into C. The substring algebra is an example of an Abstract Data Type (ADT): the actual implementation of strings is hidden from the application programmer. Much recent research has studied general mechanisms for incorporation of ADT's into programs from libraries. Unfortunately, as Section 7 will show, the substring algebra cannot readily be implemented as a library of subroutines. Section 2 defines the most fundamental primitives, applications of which are shown in Section 3 where they are used to define other functions to access substrings and Section 4 where they are used to define pattern matching. Section 5 introduces additional primitives for modification of substring values and Section 6 uses all the primitives to show that the algebra implements universal computability. Sections 7 and 8 discuss the implementations of the Algebra and experience with it, while Section 9 describes a few open problems. \heading{2. Substring Primitives} Consider the problem of finding words in a text. If we have one word and want to find the next, we first must find the leading character of the next word. For simplicity we asume that any non-blank character starts a word and write the algorithm in \ness{Ness} as \formatnote{.ne 2.5i} \example{-- NextNonBlank(\italic{w}) assumes \italic{w} is a marker for a word -- in a base string and returns a marker for the first -- non-blank character after the end of that word. -- If there is no such character, the function returns -- an empty marker at the end of the base string. -- function NextNonBlank(\italic{w}) == \{ marker \italic{c}; -- will refer to a character of the text \italic{c} := next(\italic{w}); -- start with the character after w while \italic{c }= " " do -- skip blanks \italic{c} := next(\italic{c}); -- advance c to next character return \italic{c}; -- return the present value of c \} } In NextNonBlank(), \italic{w} and \italic{c} are \italic{marker} values which encode not only a particular string, but also the position of that string within some larger string. Each call on next(\italic{c}) returns a reference to the character at the position one past the substring represented by \italic{c}; this reference is then assigned to \italic{c}. In the Icon language, the underlying string would be a global value; in the substring algebra, it is implicit in the value of the variable. Each variable in the program may refer to a portion of a different base string. A base string is a sequence of characters. A \italic{character} is an understood, but undefined, primitive object. Examples include: A, a, 1, : , $, \formatnote{\\(fi, \\(*a, \\(if , \\(->} , . A character may be unrelated to others, or be part of an alphabet (say, latin letters) or an extended alphabet (say, ASCII); the decision is made when the character is entered into the system, either as part of a program or as part of a data file. It is immaterial to the algebra whether a bold letter is a different character than the corresponding plain letter, although for most applications it may be preferable to have them be the same character and to have the programming language provide other functions for manipulating the styles of strings. Such functions are beyond the scope of this paper. To formally define the values used in this algebra, we will introduce the notion of a \italic{substring marker value}, which represents a piece of a string. (Values will not be written this way in programs.) In the notation, a pair of angle brackets delimits a sequence of characters: < s1 c > The identifiers appearing within the angle brackets are meta-variables which refer to individual characters or to sequences of zero or more characters. More commonly a marker value will also contain square brackets: \bold{Definition:} A \italic{substring marker value} (or "\italic{marker}") is written as < s1 [ s2 ] s3 > where each s\subscript{\italic{i}} is a sequence of zero or more characters. The portion s2 is the \italic{marked} or delimited portion of the string. The entire string < s1 s2 s3 > is the \italic{base} of the marked value. If s2 is of length zero, the marker is an \italic{empty} marker. It may appear that the definitions below require copying strings; the intended interpretation--and the implementation of \ness{Ness}--does not require copying strings for any of these functions other than concatenation. Traditional programming constructs have the following behavior with respect to substring marker values: \bold{"}\italic{some text}\bold{\bold{"} => < [ "}\italic{some text}\bold{" ] >} \leftindent{ A string constant returns a marker for the entire string.} \bold{< s1 [ s2 ] s3 > ~ < s4 [ s5 ] s6 > => < [ s2 s5 ] >} \leftindent{ Concatenation is written with "~" and constructs a new string composed of the juxtaposition of the arguments, returning a marker for the entire value. (Concatentation is not necessarily primitive. A redefinition is given when the algebra is extended in Section 5.) } \bold{< s1 [ s2 ] s3 >} \italic{relop} \bold{< s4 [ s5 ] s6 > => s2} \italic{relop} \bold{ s5} \leftindent{Comparison of marker values is defined to be string comparison of the delimited portion.} \bold{print(< s1 [ s2 ] s3 >) => s2} is printed \leftindent{The printed value for a marker value is taken to be the delimited portion.} \bold{marker var1, var2, ...} \indent{Declares var1, var2, . . . to be marker variables.} \bold{f(< s1 [s2 ] s3 >)} passes the entire substring marker value to the actual parameter. \leftindent{In the examples all function arguments are markers and are not declared. Parameters are call-by-value.} The algebra of substring expressions has the following primitive operations; their arguments and values are all substring marker values. \bold{start(< s1 [ s2 ] s3 >) => < s1 [] s2 s3 >} \leftindent{ Start() returns a marker both of whose limits are at the beginning of the argument. } \bold{next(< s1 [ s2 ] c s3 >) => < s1 s2 [ c ] s3 > next(< s1 [ s2 ] >) => < s1 s2 [] >} \leftindent{Next() returns a marker for the character following the argument. If the argument was at the end of its base, next() returns the end of the base.}\bold{base(< s1 [ s2 ] s3 >) => < [ s1 s2 s3 ] >} \leftindent{Base() returns a marker for the entire string surrounding the argument.} \bold{ extent(< s1 [ s2 ] s3 >, < s4 [ s5 ] s6 >) \leftindent{ => < s1 [ s7 ] s6 >, if < s1 s2 s3 > \formatnote{\\}(== < s4 s5 s6 > \leftindent{\leftindent{\leftindent{\leftindent{& < s2 s3 >\formatnote{\\}(== < s7 s6 >}}}} => < s4 s5 [ ] s6 >, if < s1 s2 s3 > \formatnote{\\}(== < s4 s5 s6 > \leftindent{\leftindent{\leftindent{\leftindent{& < s1 > \formatnote{\\}(== < s4 s5 s8 >}}}} => < [ "ERROR" ] >, otherwise}} \leftindent{Extent(a, b) produces a marker extending from the beginning of its first argument to the end of its second argument. If the second argument ends before the start of the first, the result is an empty marker at the end of the \italic{second} argument. The constant string "ERROR" is produced if the arguments are not equivalent. (The precise meaning of \formatnote{\\}(== will be made clear below. For now, we remark that the implementation of extent() does \italic{not} require testing the equality of the argument strings.)} Figure 1 illustrates the effect of start(), next(), base(), and extent(). For illustrative purposes we prove in some detail that NextNonBlank() returns a value meeting its specification. The proof is by induction on the number of blanks following the marked portion of \italic{w}. \bold{Theorem: } NextNonBlank(< s1 [ w ] b1 ... b\italic{n} x s2 >) returns the value < s1 w b1 ... b\italic{n} [ x ] s2 > and NextNonBlank(< s1 [ w ] b1 ... b\italic{n} >) returns < s1 w b1 ... b\italic{n} [] >, where w is the text of \italic{w}, the b\italic{i} are blanks, \italic{n}\formatnote{\\(>=}0, x is a non-blank, and the s\italic{i} are arbitrary sequences of characters. \bold{Proof: }The invariant of the loop just before testing the predicate is \description{\indent{(i) the marked portion of \italic{c} is a single character or an empty mark at the end of the base string, and (ii) the marked portion of extent(next(\italic{w}), start(\italic{c})) is all blanks.}} Part (i) is preserved throughout because c is always assigned the result of next(). The meaning of the expression in part (ii) is "all characters after \italic{w} and before \italic{c}". This can be verified with reference to the definition by supposing that \italic{c} is \leftindent{< s1 w b\subscript{1} ... [ b\italic{i} ] ... b\italic{n} x s2 >} With this c, the extent() expression in (ii) evaluates to \leftindent{extent(next(\italic{w}), start(\italic{c})) = extent(next(< s1 [ w ] b\subscript{1} ... b\italic{i} ... b\italic{n} x s2 >), \leftindent{start(< s1 w b\subscript{1} ... [ b\italic{i} ] ... b\italic{n} x s2 >))} = extent(< s1 w [ b\subscript{1} ] ... b\italic{i} ... b\italic{n} x s2 >, \leftindent{< s1 w b\subscript{1} ... [] b\italic{i} ... b\italic{n} x s2 >)} = < s1 w [ b\subscript{1} ... ] b\italic{i} ... b\italic{n} x s2 >} The meaning is similar if \italic{c} is x or if x and s2 are absent and \italic{c} is an empty marker after b\italic{n}. If the invariant is preserved and the function returns c, then c must be the first non-blank after the end of w or the end of the base: part (i) guarantees that c is a single character or the end of the base, part (ii) guarantees that the only characters between w and c are blanks, and the loop predicate guarantees that c is not a blank. It remains to verify part (ii) of the invariant. Initially, \italic{i} is zero and the predicate is trivially true because the extent() yields an empty marker. If we enter the loop body, \italic{c} must be one of < s1 w b\subscript{1} ... [ b\italic{i} ] ... b\italic{n} x s2 > , < s1 w b\subscript{1} ... b\italic{i} ... [ b\italic{n} ] x s2 > , or < s1 w b\subscript{1} ... b\italic{i} ... [ b\italic{n} ] > . These are converted by the loop body to, respectively, < s1 w b\subscript{1} ... b\italic{i} [ b\italic{\subscript{i}}\subscript{+1} ] ... b\italic{n} x s2 > , < s1 w b\subscript{1} ... b\italic{i} ... b\italic{n} [ x ] s2 > , and < s1 w b\subscript{1} ... b\italic{i} ... b\italic{n} [] > , all of which again satisfy part (ii). Thus the invariant is preserved and the theorem is proved. \formatnote{\bold{\\(sq}} With the aid of NextNonBlank() we now define NextWord(). In \ness{Ness} the convention for unsuccessful searches is that they return an empty marker at the beginning of the original argument. Our definition of NextWord() adheres to this convention: \formatnote{.ne 3.2i} \example{-- NextWord(\italic{w}) assumes \italic{w} is a word in a string and returns -- a marker for the next word. A "word" is any text -- delimited by blanks or the end of the base string. -- If there is no such word, the function returns start(\italic{w}). function NextWord(\italic{w}) == \{ marker \italic{a}; \italic{a} := NextNonBlank(\italic{w}); if \italic{a} = "" then -- reached end of base string return start(\italic{w}); \italic{w} := \italic{a}; while \italic{a} /= "" & \italic{a} /= " " do -- scan for next blank \italic{a} := next(\italic{a}); -- now \italic{a} points to the first blank after a non-blank after\italic{ w} -- or it is an empty at the end of its base return extent(\italic{w}, start(\italic{a})); \}} \bold{Theorem:} NextWord() correctly meets its initial comment. \bold{Proof:} The argument \italic{w} to NextWord() may be initially \italic{w} = < s1 [ w ] sb > where sb is a sequence of blanks. In this case, the specification of NextNonBlank gives us that \italic{a} = < s1 w sb [] > so the \keyword{if} predicate is satisfied and the function returns start(\italic{w}), as specified. The alternative and more interesting values for \italic{w} are < s1 [ w1 ] sb x w2 bl s3 > or < s1 [ w1 ] sb x w2 > where w2 is a sequence of non-blank characters, bl is a blank, and s3 is some sequence of characters. In this case, the specification of NextNonBlank() provides that \italic{a} is < s1 w1 sb [ x ] w2 bl s3 > or < s1 w1 sb [ x ] w2 > and one of these is subsequently assigned to \italic{w}. By an argument similar to that for NextNonBlank(), the while loop gives \italic{a} the value < s1 w1 sb x w2 [ bl ] s3 > or < s1 w1 sb x w2 [] > . In each case, the extent() constructs a correct return value for the function: < s1 w1 sb [ x w2 ] bl s3 > or < s1 w1 sb [ x w2 ] > . \formatnote{\bold{\\(sq}} In order for a set of functions to be teachable and memorable, they should be based on an underlying set of functions that are as small as possible. The next section will present a number of additional substring functions all of which can be defined in terms of the primitives above. To show that the primitive set cannot be reduced we have: \bold{Theorem(Necessity):} The four primitive functions--start(), next(), base(), and extent()--are all necessary for computation with the algebra. That is, none can be expressed as a functional composition of the others. \bold{Proof:} We wish to demonstrate for each of the primitives, P, that there is no definition "function P(\italic{m}) == \italic{E}" which behaves as defined above for P and yet does not contain P in the expression \italic{E}. We do this by exhibiting a particular value for \italic{m} and argue for each primitive that no such expression \italic{E} exists that converts this value appropriately, and therefore no expression \italic{E} exists which implements P for all arguments. The particular value \italic{v} is < "ab" [ "cd" ] "ef" >. Note first that \leftindent{next(\italic{v}) = < "abcd" [ "e" ] "f" >, start(\italic{v}) = < "ab" [] "cdef" >, and base(\italic{v}) = < [ "abcdef" ] >.} For extent() no \italic{E} can exist because the value returned may have to be of any length and the other functions return only markers of zero, one, or all the characters of a base. For base() no \italic{E} can exist because none of the other functions can otherwise generate a marker beginning before the left bracket of \italic{v}. For next() no \italic{E} can exist because no other function creates a marker that starts at the end of \italic{v}. For start() there can be no \italic{E} whose return value is generated by base() or next() because they generate values with end brackets after the end of \italic{v}. If the return value is generated by extent(), its second argument must end at the start of \italic{v}, but it must ultimately have gotten this value from base() or next(), which it cannot have done. Since none of the functions can be expressed in terms of the others, all are necessary. \formatnote{\bold{\\(sq} } We have experimented briefly with various alternative sets of primitive functions. For instance, the symmetry of the algebra permits previous() instead of next() or end() instead of start(); but either would emphasize right-to-left processing instead of the more natural left-to-right processing. We could replace base() with startofbase() which gives a zero-length marker at the start of the base; the present base() function could then be defined with a next() loop to find the end of the base and an extent() to build the value. Next() could return an empty marker after the following character. Experimentation showed that these and other alternatives were not as convenient for programming. \heading{3. Substring Functions} Many substrings of the base for marker \italic{m} can easily be computed from \italic{m} with the substring algebra. The ones that follow are illustrated in Figure 2. \bold{end(\italic{m})} - Returns a marker for the empty substring just after \italic{m}. \example{function end(\italic{m}) == return start(next(\italic{m}));} \bold{rest(\italic{m})} - Returns a marker for all characters of \italic{m} other than the first. If \italic{m} is empty, so is rest(\italic{m}). \example{function rest(\italic{m}) == return extent(next(next(start(\italic{m}))), \italic{m}); } \{Note that the definition of rest() exploits the clause in the definition of extent() which specifies that an empty result is at the end of its second argument.\} \bold{first(\italic{m})} - Returns the first character of \italic{m.} If \italic{m} is empty, so is first(\italic{m}). \example{function first(\italic{m}) == return extent(\italic{m}, start(rest(\italic{m})));} \bold{second(\italic{m})} - Returns a marker for the character following first(\italic{m}), if there is one. \example{function second(m) == return first(rest(m));} \bold{advance(\italic{m})} - Returns a marker extending from just after the first character of \italic{m} to just after next(\italic{m}). In general advance(\italic{m}) will have the same number of characters as \italic{m}, but it may be shorter if the end of \italic{m} is at the end of the base string. \example{function advance(\italic{m}) == return extent(end(front(\italic{m})), next(\italic{m}));} \bold{front(\italic{m})} - Returns a marker for the first character after start(\italic{m}), if there is one, otherwise \italic{m} must be empty at the end of its base and this value is returned. Unlike first(), front() returns a character for all cases other than the very end of the base. \example{function front(\italic{m}) == return next(start(\italic{m}));} \bold{allprevious(\italic{m})} - Returns a marker for the substring of the base of \italic{m} that precedes the start of \italic{m}. \example{function allprevious(\italic{m}) == return extent(base(\italic{m}), start(\italic{m}));} \bold{allnext(\italic{m})} - Returns a marker for the substring of the base of \italic{m} that follow the end of \italic{m}. \example{function allnext(\italic{m}) == return extent(end(\italic{m}), base(\italic{m}));} \bold{last(\italic{m})} - Returns the last character of \italic{m}. If \italic{m} is empty, so is last(\italic{m}). \example{function last(\italic{m}) == \{ if rest(\italic{m}) = "" then return \italic{m}; else return last(rest(\italic{m})); \}} \{The above implementation of \italic{last}() would be grossly inefficient in practice. Fortunately it can be implemented by scanning backward in the base string. This can safely be done if there is a maximum length to the encoding of each character and the byte value that introduces a multi-byte encoding cannot appear within an encoding.\} \bold{previous(\italic{m})} - Returns a marker for the character preceding \italic{m}. If \italic{m} is at the beginning of its base string, previous(\italic{m}) returns the value start(\italic{m}). \example{function previous(\italic{m}) == last(extent(base(\italic{m}), start(\italic{m}))); } For the purposes of later theorems we prove the correctness of some of these functions: \bold{Lemma (Rest()):} The function rest(), defined as above, has the value \leftindent{(i) rest(< s1 [ c s2 ] s3 >) => < s1 c [ s2 ] s3> and (ii) rest(< s1 [] s3 >) => < s1 [] s3 >.} \bold{Proof:} The proof of (i) has three cases depending on the lengths of s2 and s3. When s2 has at least one character we write s2 as < c2 s4 > and the proof proceeds thus: rest(< s1 [ c c2 s4 ] s3 >) = extent(next(next(start(< s1 [ c c2 s4 ] s3 >))), < s1 [ c c2 s4 ] s3 >) = extent(next(next(< s1 [] c c2 s4 s3 >)), < s1 [ c c2 s4 ] s3 >) = extent(next(< s1 [ c ] c2 s4 s3 >), < s1 [ c c2 s4 ] s3 >) = extent(< s1 c [ c2 ] s4 s3 >), < s1 [ c c2 s4 ] s3 >) = < s1 c [ c2 s4 ] s3 > The second case is where s2 is empty and s3 has one or more characters. In the third case s2 and s3 are both empty. In each of these cases the marker is reduced to a empty substring at its former end. These cases can be verified by an argument similar to that of the first. For part (ii) we observe that the first argument to extent() is next(next(start(\italic{m}))), which cannot yield a marker starting before the beginning of \italic{m} and the second argument is \italic{m}, which ends at the end of \italic{m}. Since \italic{m} is empty, the extent() must yield a marker equivalent to \italic{m}.\formatnote{\bold{ \\(sq}} \bold{Lemma (Last()):} The function last() defined as above has the value \leftindent{(i) last(< s1 [ s2 c ] s3 >) => < s1 s2 [ c ] s3 > and (ii) last(< s1 [] s3 >) => < s1 [] s3 >.} \{That is, last(\italic{s}) produces a marker for the last character in \italic{s} if \italic{s} has any characters and otherwise returns \italic{s}.\}\bold{Proof: } Part (i) when s2 is of length zero and part (ii) both follow directly from the Rest() Lemma. For part (i) where s2 is of length greater than zero we argue by induction. Suppose s2 is < c s4 >. In this case the predicate fails (by the Rest() Lemma) and so the value is last(rest(< s1 [ c s4 ] s3 >) = last(< s1 c [ s4 ] s3 >) Since s4 is a shorter sequence than s2, the inductive hypothesis applies and the theorem is proved. \formatnote{\bold{ \\(sq}} \bold{Lemma (Previous()):} The function previous() has the value \leftindent{(i) previous(< s1 c [ s2 ] s3 >) => < s1 [ c ] s2 s3 > and (ii) previous(< [ s2 ] s3 >) => < [] s2 s3 >} \bold{Proof:} By the definitions of base(), start(), extent(), and last(): previous(< s1 c [ s2 ] s3 >) = last(< [ s1 c ] s2 s3 >) = < s1 [ c ] s2 s3 > and previous(< [ s2 ] s3 >) = last(< [] s2 s3 >) = < [] s2 s3 > In both cases the desired value is computed. \formatnote{\bold{\\(sq}} With the aid of the substring functions, it is possible to write an expression for any substring of a string. To demonstrate this, consider the set of \italic{all} substrings of a string. This set consists of each instance of a substring starting at one position in the string and continuing to the same or another, later postion. Here are functions to print all the substrings of a string: \example{function printsubstrings(\italic{s}) == \{ printsubsub(\italic{s}, \italic{s}); if \italic{s} /= "" then printsubstrings(rest(\italic{s})); \} function printsubsub(\italic{t}, \italic{s}) == \{ print extent(\italic{s}, start(\italic{t})); if \italic{t} /= "" then printsubsub(rest(\italic{t}), \italic{s}); \}} It is not difficult to show that printsubstrings(\italic{s}) prints all substrings of \italic{s}. We begin with a lemma. \bold{Lemma: (Tail Recursion)} If P is an operation and Q is a sequence of zero or more variables each preceded by a comma, then the function f() defined by function f(\italic{x} Q) == \{ P(\italic{x} Q); if \italic{x} /= "" then f(rest(\italic{x}) Q); \} performs P once for each \italic{tail} of \italic{x}, including the final empty substring. That is, if \italic{x} is < s1 [ c1 c2 . . . c\italic{n} ] s3 > then P is executed for each of \leftindent{ < s1 [ c1 c2 . . . c\italic{n} ] s3 >, < s1 c1 [ c2 . . . c\italic{n} ] s3 >, . . ., < s1 c1 c2 . . . [ c\italic{n} ] s3 >, and < s1 c1 c2 . . . c\italic{n} [] s3 >.} \bold{Proof:} If \italic{x} is < s1 [] s3 >, then \italic{n} is zero and P is executed once; the \keyword{then} clause is not executed because \italic{x} = "" is True. When \italic{n} > 0 we argue by induction. A call to f() evaluates P once for the current value of \italic{x} and then calls f recursively for rest(\italic{x}). By the Rest() Lemma, rest(\italic{x}) is a tail of \italic{x} so \italic{n} is one less and the general case holds by induction. \formatnote{\bold{\\(sq}} \bold{Lemma (printsubsub):} The call printsubsub(\italic{s}, \italic{s}) prints all substrings of \italic{s} that begin at start(\italic{s}). \bold{\{Proof:} By the Tail Recursion Lemma, printsubsub(\italic{s}, \italic{s}) executes print(extent(\italic{s}, start(\italic{t}))) for \italic{t} being each tail of \italic{s}. This is exactly the subsets of \italic{s} that begin at the beginning of \italic{s}. \formatnote{\bold{\\(sq}} \bold{Lemma (printsubstrings):} The call printsubstrings(\italic{s}) print all substrings of \italic{s}. \bold{Proof:} By the Tail Recursion Lemma, printsubstrings(\italic{s}) executes printsubsub(\italic{s}, \italic{s}) for \italic{s} being each tail of the initial \italic{s}. By the preceding lemma, this call prints the substrings beginning at each position within \italic{s}, which is the entire set of substrings. \formatnote{\bold{\\(sq}} \bold{Theorem (Sufficiency):} The substring algebra is sufficient to generate all substrings of the base of a string. \bold{Proof:} By the preceding Lemma, if \italic{s} is a string, the call printsubstrings(base(\italic{s})) will print all substrings of the base of \italic{s}. Since they are printed, they must have been generated. Since only the functions of the algebra have been used to operate on string values, those functions must be sufficient. \formatnote{\bold{\\(sq}} Note that the Sufficiency Theorem proves that all substrings can be generated, but not that any specified substring or set of substrings can be generated. This more general result will be established in Section 6. \heading{4. Pattern Matching} Pattern matching is a fundamental operation on string values. SNOBOL, as pointed out in [Griswold, 1980], even has two distinct linguistic components: one for traditional computation and one for pattern matching. The algebra as described so far has no provision for pattern matching at all, however, it is not difficult to express pattern match primitives within the algebra. In a practical implementation, these would be hand coded for speed. One of the difficulties in defining pattern match functions is that a pattern match needs to return two facts: whether the match succeeded and, if so, the location of the matching substring. This problem has usually been solved by introduction of \italic{failure} as a control flow mechanism. It is not the purpose of this paper to consider control-flow architectures; failure is an elegant tool and can be used in conjunction with the substring algebra. However, failure is not necessary because marker values are already returning two facts: the two ends of a substring. By convention, a pattern matching operation in the algebra returns the matched string for success. For failure the operation returns an \italic{empty string at the beginning of the argument susbstring.} This convention has turned out to be the most useful of the various possibilities; it allows nested searches to have suitable behaviors. With this convention, the \ness{Ness} implementation of the algebra offers five pattern match functions. Each searches the substring extent(\italic{m}, end(base(\italic{m}))) for some substring matching a criterion: \bold{search(\italic{m, target})} - If successful, returns a marker surrounding the first substring of the source that is equal to \italic{target}. \bold{match(\italic{m, target})} - Determines whether the source begins with a substring identical to \italic{target}; if so, it returns a marker for that substring. \bold{span(\italic{m, clist})} - Returns a marker for all characters of the source from its beginning to just before the first character not in \italic{clist}. That is, span matches the longest initial substring of the source that is composed of characters from \italic{clist}. \bold{anyof(\italic{m, clist})} - Finds the first character in the source that is one of the characters in \italic{clist} and returns a marker for the character. \bold{token(\italic{m, clist})} - Searches the source for the first substring consisting of characters from \italic{clist} and returns a marker for the substring. \example{function token(\italic{m}, \italic{pat}) == return span(anyof(\italic{m}, \italic{pat}), \italic{pat});} Here are the definitions of two of the pattern matching functions in terms of the primitives. The others are similar. The most fundamental pattern match is search(\italic{m},\italic{ pat}), which searches for an exact match of its second argument: \example{ function search(\italic{m}, \italic{pat}) == \{ marker \italic{pf, startm, tm, tp}; \italic{startm} := start(\italic{m}); \italic{m} := front(\italic{m}); if \italic{pat} = "" then return \italic{startm}; \italic{pat} :=\italic{ pat} ~ ""; -- copy \italic{pat} \italic{pf} := front(\italic{pat}); while\italic{ m} /= "" do \{ -- search for first char of \italic{pat} while \italic{m} /= \italic{pf} do \{ \italic{m} := next(\italic{m}); if \italic{m} = "" then return \italic{startm}; \} -- compare \italic{pat} at \italic{m} -- if (\italic{pat} is at \italic{m}) -- return \italic{pat} at \italic{m}; \italic{tm} := \italic{m}; \italic{tp} := front(\italic{pat}); while \italic{tm} /= "" & \italic{tm} = \italic{tp} do \{ \italic{tm} := next(\italic{tm}); \italic{tp} := next(\italic{tp}); \} if \italic{tp} = "" then return extent (\italic{m}, start(\italic{tm})); else\italic{ m }:= next(\italic{m}); \} return \italic{startm}; -- failure \} } In this definition, \italic{m} is always a single character. The inner \keyword{while} loop advances \italic{m} until it is equal to the first character of \italic{pat}. When it is, subsequent characters are checked against the rest of \italic{pat}. The outer \keyword{while} loop continues this process until a match is found or the end of base(\italic{m}) is reached. The span function clearly illustrates the utility and implementation of the convention of returning an empty string for failure of a search: \formatnote{.ne 1.8i} \example{function span(\italic{s}, \italic{clist}) == \{ marker\italic{ m}; \italic{m} := front(\italic{s}); \italic{clist} := "" ~ \italic{clist}; -- copy \italic{clist} to limit the search while search(\italic{clist}, \italic{m}) /= "" do \italic{m} := next(\italic{m}); return extent (\italic{s}, start(\italic{m})); \}} In this function, \italic{m} is always a single character. It is checked by the search() call to see if it is in \italic{clist} and if so, \italic{m} advances. If not, the desired string extends from the start of \italic{s} to the start of \italic{m}. The reader is invited to study what happens if the first character of \italic{s} is not in \italic{clist} or if all characters of \italic{s} are in \italic{clist}. The pattern functions above can easily be incorporated sequentially in a program to check for a pattern which is a sequence of items. However, it is not as clear that complex patterns can be implemented simply. To understand this problem, the author examined a collection of clever SNOBOL algorithms [Gimpel, 1976]. The measure of a complex pattern was taken to be the appearance of the operator "|" which is the most general way in which back tracking is required by a pattern. Of the 148 algorithms in the collection only 36 utilize the "|" and only an average of twice per algorithm. Moreover, about half the instances are concerned with end conditions* rather than real alternatives. In the substring algebra, end conditions are more easily dealt with because the ends of the base string can be referred to directly. _________________________________ * Of the 73 patterns that contained "|", 30 used it only for " | REM", " | NULL", or " | RPOS(0)". _________________________________ In addition to complex patterns, SNOBOL is an interpretive systemand offers many clever and unusual facilities. However the disadvantages of their complexity and diversity are many, as summed up in [Icon]: \leftindent{ (1) An excessively large vocabulary. (2) Complexity of the pattern matching algorithm. (3) Unnecessary backtracking and lack of control over the pattern-matching algorithm. (4) Confusion between pattern construction and pattern matching. (5) Difficulties with program structuring, especially the necessity of using side-effects. (6) Inefficiency inherent in run-time construction of patterns. (7) Dichotomy of languages, with a further increase in total vocabulary and a linguistic schism. (8) Lack of a mechanism for defining matching procedures. } The solution proposed in Icon is to develop new control constructs based on failure such that pattern matching is not a facility of the language but can be expressed very cleanly. There is no conflict between the constructs developed in Icon and those here; marked substrings could easily be the basic string representation in Icon. However, with marked substrings we have found few tasks where pattern matching was an issue. It appears that it is sufficient to be able to refer to substrings of a base and access adjacent strings through functions calls. One of the examples often cited for complex pattern matching is that of recognizing arithmetic expressions. Simple recognizers for such expressions can easily be expressed in SNOBOL. For instance the following set of SNOBOL patterns read as though they were a grammar themselves. \leftindent{PRIM = "x" | "y" | "z" | "(" *EXP ")" ADDOP = "+" | "-" MULOP = "*" | "/" TERM = PRIM | *TERM MULOP PRIM EXP = TERM | *EXP ADDOP TERM} (The prefix asterisk operators are peculiar to SNOBOL; they defer evaluation of forward references. The grammar here is an adaptation of one in [Griswold, 1980], which does not give an Icon recognizer for the grammar.) Using the subexpression algebra, a recognizer for the grammar can be written as: \example{function acceptPrim(\italic{s}) == \{ if search("xyz", front(\italic{s})) /= "" then return front(\italic{s}); if front(\italic{s}) = "(" then return extent(\italic{s}, next(acceptExp(next(front(\italic{s}))))); return start(\italic{s}); \} function acceptTerm(\italic{s}) == \{ marker \italic{t}; \italic{t} := acceptPrim(\italic{s}); while search("*/", next(\italic{t})) /= "" do \italic{t }:= acceptPrim(next(next(\italic{t}))); return extent (\italic{s}, \italic{t}); \} function acceptExp(\italic{s}) == \{ marker \italic{t}; \italic{t} := acceptTerm(\italic{s}); while search("+-", next(\italic{t})) /= "" do \italic{t} := acceptTerm(next(next(\italic{t}))); return extent (\italic{s}, \italic{t}); \}} Note that each function adheres to the convention of returning the string it matches or else an empty string at the beginning of its initial argument. The acceptXxx functions are undeniably longer than the SNOBOL patterns, but they have many advantages. It is easier to see how to extend the algebraic version to handle white-space, identifiers of indefintie length, integer constants, syntax errors, and generation of code. Indeed a version that handles all these and interprets the resulting pseudo-code was coded and debugged in four hours. Traditionally it is challenging to permit a compiler to accept identifiers of any length, but this was accomplished trivially with the span() function. \heading{5. String Modification} Functional programming has been an important recent research area emphasizing the desirability of side-effect-free computation. In such systems, values once created never change. The algebra presented so far is completely functional: values are created as constants or with concatenation and thereafter remain inviolate. Efficiency is gained because substring values need not be copies: they are references to pieces of existing strings. Some programmers, for some applications, nonetheless desire to modify values rather than create new ones. The simplest way to accomodate this desire is to augment the algebra with an operation which appends a string to the end of an existing string. We will use the notation ~:= for this operation, even though it is not an exact analog of concatenation. Since it will modify an existing string, we will represent this string by variable \italic{m} with initial value < s1 [ s2 ] s3 >. The operation is then defined as \bold{\italic{m} ~:= < s4 [ s5 ] s6 > \leftindent{\leftindent{=> \italic{m} := < s1 [ s2 s5 ] >, s3 is empty => < [ "ERROR" ] >, otherwise}}} \indent{The marked value of the second operand is inserted at the end of the first operand. The variable which is the first operand is altered to refer to both the old and new text. The operation sets \italic{m} to the value "ERROR" if there are any characters after the right bracket in the first operand.} With append, it is possible to efficiently produce an altered copy of an existing string. The existing string is processed from left to right and pieces are appended to the result string as they become known. For general string modification algorithms, ~:= may not satisfy some people. Therefore a third version of the algebra can be defined by introducing two additional primitives, replace() and newbase(). To keep the underlying algebra as small as possible, these new functions are then used to redefine append and concatenation. The replace() function is defined formally by: \bold{replace(< s1 [ s2 ] s3 >, < s4 [ s5 ] s6 >) \leftindent{\leftindent{=> < s1 [ s5 ] s3 >, if < s1 [ s2 ] s3 > is not a constant => < [ "ERROR" ] >, otherwise}}} \indent{Replace(\italic{m}, \italic{s}) modifies the string marker value \italic{m} so its marked portion now contains the marked portion of string \italic{s} instead of its former value. The value returned is a marker delimiting the new copy of the replacement value. All strings \formatnote{"\\(=="} to < s1 [ s2 ] s3 > are also modified (see below).} This function replaces one non-empty substring with another, but can also perform an insertion or deletion. For insertion, an empty marker is replaced with non-empty text; for deletion, a non-empty substring is replaced with empty text. Since the purpose of replace() is to modify existing values, rather than create new ones, the definition of \formatnote{\\(==} used in the definitions of extent() and replace() must indicate that the two markers are not only the same value, but they are the same instance of that value. We model this situation formally by representing the state of memory as a sequence of base strings: \{< ... [ s2 ] ... >, < ... [ s5 ] ... > , . . . \} To indicate that markers share the same base, we label the brackets of each marker. Thus two markers on the same base could look like: < s1 [\subscript{\formatnote{\\}(*a} s2 [\subscript{\formatnote{\\}(*b} s3 ]\subscript{\formatnote{\\}(*a} s4 ]\subscript{\formatnote{\\}(*b} s5 > where the marked value of \formatnote{\\}(*a is < s2 s3 > and that of \formatnote{\\}(*b is < s3 s4 >. We require that the labels on all pairs of brackets be unique, so a label identifies both a base and a marked substring within that base. Two base strings have the relation base(\formatnote{\\}(*a) \formatnote{\\}(== base(\formatnote{\\}(*b) when both \formatnote{\\}(*a and \formatnote{\\}(*b are labels for markers within the same < . . . > pair. The value returned by replace(\formatnote{\\}(*a, \formatnote{\\}(*b) is a marker label for the copy of the marked portion of \formatnote{\\}(*b that has replaced the former marked portion of \formatnote{\\}(*a. Replace(\formatnote{\\}(*a, \formatnote{\\}(*b) must affect any marker formerly on the base of \formatnote{\\}(*a and ending after the start of \formatnote{\\}(*a. Any marker bracket [\subscript{\formatnote{\\}(*g} or ]\subscript{\formatnote{\\}(*g} that formerly appeared after ]\subscript{\formatnote{\\}(*a} must remain between the characters it originally separated. Brackets formerly within [\subscript{\formatnote{\\}(*a} . . . ]\subscript{\formatnote{\\}(*a} and brackets formerly at the same place as one of these may have to be adjusted. The simplest rule for this adjustment can be described as inserting the new text just before all brackets at the position of the ]\formatnote{\\}(*a bracket and then deleting the text formerly labelled by \formatnote{\\}(*a. Formally, this is described by the rules below, where rule (1) simply makes a copy, \formatnote{\\}(*w, of the replacement text in case \formatnote{\\}(*a and \formatnote{\\}(*b are on the same base. Then rules (2) and (3) move the brackets, perform the replacement, and discard \formatnote{\\}(*w. In these rules \formatnote{\\}(*w is a unique marker label, s\italic{i} is a sequence of zero or more characters, c is a character, b\italic{i} is a sequence of zero or more brackets, and sb\italic{i} is a mixed sequence of characters and brackets whose brackets taken separately are denoted by b\italic{i} and whose characters taken separately are denoted by s\italic{i}. \bold{replace(\formatnote{\\}(*a, \formatnote{\\}(*b): (1) \{ . . . < sb1 [\subscript{\formatnote{\\}(*a} sb3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . < sb5 [\subscript{\formatnote{\\}(*b} sb6 ]\subscript{\formatnote{\\}(*b} sb7 > . . . \}, => \{ . . . < sb1 [\subscript{\formatnote{\\}(*a} sb3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . < sb5 [\subscript{\formatnote{\\}(*b} sb6 ]\subscript{\formatnote{\\}(*b} sb7 > . . . < [\subscript{\formatnote{\\}(*w } s6 ]\subscript{\formatnote{\\}(*w} > \} \leftindent{(2) \{ . . . < sb1 [\subscript{\formatnote{\\}(*a} sb2 c b3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . < [\subscript{\formatnote{\\}(*w} s6 ]\subscript{\formatnote{\\}(*w} > \} } \leftindent{\leftindent{=> \{ . . . < sb1 [\subscript{\formatnote{\\}(*a} b2 s6 b3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . \}}} \leftindent{(3a) \{ . . . < sb1 c b2 [\subscript{\formatnote{\\}(*a} b3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . < [\subscript{\formatnote{\\}(*w } s6 ]\subscript{\formatnote{\\}(*w} > \} } \leftindent{\leftindent{=> \{ . . . < sb1 c [\subscript{\formatnote{\\}(*a} s6 b2 b3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . \}}} \leftindent{(3b) \{ . . . < b2 [\subscript{\formatnote{\\}(*a} b3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . < [\subscript{\formatnote{\\}(*w} s6 ]\subscript{\formatnote{\\}(*w} > \} } \leftindent{\leftindent{=> \{ . . . < [\subscript{\formatnote{\\}(*a} s6 b2 b3 ]\subscript{\formatnote{\\}(*a} sb4 > . . . \}}} } These rules are illustrated in Figure 3. However, to create robust algorithms, it is probably best to assume that these rules are unknown and write the algorithm so it will work no matter what the rules are. As an example of replace(), here is a procedure to expand the tabs in string \italic{m} by replacing them with enough spaces so the text after a tab is moved to the next available position among 9, 17, 25, 33, . . . : \example{function ReplaceTabs(\italic{m}) == \{ marker \italic{f}, \italic{tab}, \italic{eight}; \italic{eight} := " "; -- 8 spaces \italic{tab} := \italic{eight}; -- initial distance to tab while \italic{m} /= "" do \{ \italic{f} := first(m); \italic{m} := rest(\italic{m}); if \italic{f} = "\\t" then \{ -- replace tab with spaces replace (\italic{f}, \italic{tab}); \italic{tab} := \italic{eight}; \} else if \italic{f} = "\\n" or \italic{tab} = " " then -- newline or single space for this tab, -- start next tab \italic{tab} := \italic{eight}; else -- non-tab: shorten distance to tab stop \italic{tab} := rest(\italic{tab}); \} \} } The replace() changes a tab character into just enough spaces to fill to the next tab stop. Note the absence of arithmetic for determining the current output position. As an exercise the reader is invited to write a version of ReplaceTabs() that keeps track of tab position with integers. Observe that the formal parameter \italic{m} in ReplaceTabs() is modified in two distinct fashions: it is advanced through the base string and the base string is modified with replace(). Since parameters in \ness{Ness} are call-by-value, only the second of these will affect variables in a routine that calls ReplaceTabs(). In an implementation of the substring algebra, it is desirable that program constants not be modified. If an attempt is made to replace a portion of a constant string, the program is aborted. It may be desirable to create an empty string into which text can be inserted with replace(). For this we provide a primitive read-write constant: \bold{newbase() => < [] > } \leftindent{Creates a new, modifiable and empty, base string.} With newbase() we can now redefine concatentation and introduce an append operation: \bold{ s ~ t == base(replace(end(replace(newbase(), s)), t)).} \leftindent{The result contains the concatentation of the marked segments from \italic{s} and \italic{t}.} \bold{ v ~:= t == v := extent(v, replace(end(v), t)) , \leftindent{\leftindent{(where v is a variable).}}} \leftindent{The value of variable \italic{v} is appended with \italic{t} and \italic{v} is given the entire result as its new value.} With these definitions, one common coding sequence can be \example{\italic{t }:= newbase(); while . . . do \{ . . . \italic{t} ~:= \italic{expression}; . . . \} } The variable \italic{t} is initialized to a modifiable empty string and then text is appended to it within the loop. \heading{6. Completeness} One way to show that the substring algebra is "complete" is to show it provides universal computability as defined by a Turing machine: \bold{Theorem (Universal Computability):} The substring algebra is sufficient to simulate a Turing machine having a tape with symbols of "0" and "1", a read head which is examining one symbol of the tape, a state machine based on the symbol under the read head, and five operations: move head left, move head right, write a "0", write a "1", and halt. \bold{Proof Outline:} The non-empty portion of the tape is represented by a substring marker value with a single character marked; this is the current position of the read head. Suppose that in state S a "0" under the read head will cause operation P and transitition to state U while a "1" under the read head will cause operation Q and a transition to state V. Then state machine implementation is a collection of procedures, one for each state, having the form \formatnote{.ne 1.3i} \example{function S(\italic{t}) == \{ if \italic{t} = "0" then \{ P; U(\italic{t}); \} else \{ Q; V(\italic{t}); \} \}} The five operations are defined as converting the initial tape \italic{t} into a new tape value: \leftindent{move right: if next(\italic{t}) = "" then \italic{ t} := last(base(\italic{t}) ~ " "); else \italic{t} := next(\italic{t}); move left: if previous(\italic{t}) = "" then \italic{ t} := next(start(" " ~ t)); else \italic{t} := previous(\italic{t}); write a "0":\italic{ t} := replace(\italic{t}, "0"); write a "1":\italic{ t} := replace(\italic{t}, "1"); halt: print(\italic{t}); exit();} These operations are incorporated in place of P and Q in the procedures implementing the finite state machine. The functions do not terminate. If a halt is reached it prints the tape value and exits. All the substring functions utilized in the state machine are either primitive or have been proven to have the appropriate behavior. Therefore the collection of procedures in the substring algebra implements the Turing machine, so all functions are computable. \formatnote{\bold{\\(sq}} Note that this version of the Turing machine simulation is not functional; it utilizes the replace() function. A purely functional simulation is not difficult and may amuse the reader; however, it would add bulk without enlightenment to this paper. The Universal Computability Theorem does demonstrate the computational power of the substring algebra, but contributes little to an understanding of its practicality. It is preferable to observe that the computable functions include all substring functions and that the Sufficiency Theorem shows that all substrings can be generated. We thus have the \bold{Theorem (Completeness):} The substring algebra can compute any function over the set of all substrings of a base. \formatnote{\bold{\\(sq}} \heading{7. Implementation} To demonstrate the practicality of computing with the substring algebra, here is a quick sketch of an implementation. Each separate base string is represented by a control block which contains pointers to the ends of the stored base text and a pointer to a list of all markers on that base. The list of markers is used to find markers that must be modified for replace(); moreover, when the list is empty the base itself can be discarded. Each marker is a compound of four values: a reference to the beginning of the marked substring, a reference to the end of the marked substring, a pointer to the control block for the base, and a pointer to the next marker in the list from that base. The definitions of next(), base(), and start() in this storage structure are quite trivial, requiring only copying the argument marker and revising one or both references to the string ends. The extent operation is slightly more complex only because it must check for several conditions. Although the substring algebra is an Abstract Data Type, it poses a severe test of mechanisms for incorporating ADT's into programs from a library. The difficulty is that the lists of marker values must be maintained so every assignment and procedure call must have special handling for markers. In particular, if a temporary marker value has been passed as a parameter to a procedure, it must be discarded when the procedure exits. A real compiler can directly compile the appropriate code because it has complete control over the stack and heap. When implementing the algebra as a subroutine package, the most convenient approach is to implement a separate stack for marker values. All marker functions are then parameterless procedures which take their operands from the stack. This makes the simplest marker functions even simpler because they need only modify the top marker on the stack. In a paging environment, the best organization of the actual string texts is as a single long string of characters as described in [Hansen, 1987c]. To reduce the amount of character movement for replace(), gaps are allowed within the strings. These techniques have been incorporated in a subroutine package for C [Hansen, 1987b]. The compiler for \ness{Ness} converts its input into an equivalent C program which utilizes the subroutine package. To illustrate various aspects of the implementation, here is the function from the \ness{Ness} compiler which converts a function call into an appropriate C function call. \example{ -- DoCall(\italic{id, p, v}) processes a call to a function whose name -- is in the source text at the location given by \italic{id}, whose -- left parenthesis is at \italic{p}, and using local variables given by \italic{v.} -- Returns the character immediately after the closing ")". -- Converts " func ( arg1 , . . . argn ) " -- into " ( arg1* , . . . argn* , func* () ) " , -- where the *'s indicate translation. -- If func is not predefined, func* is func; otherwise -- it is the value found in FuncNames, where the -- form of each entry is -- ,predefinedname(),replacementname()! -- function DoCall(\italic{id, p, v}) == \{ marker \italic{t, theCall}; \italic{t} := "," ~ \italic{id} ~ "()"; -- see if the function name is pre-defined \italic{theCall} := search(\italic{FuncNames}, \italic{t}); if \italic{theCall} = "" then \italic{theCall} := \italic{t}; else -- extract the replacement name from the table \italic{theCall} := extent(end(\italic{theCall}), start(search(end(\italic{theCall}), "!"))); while \italic{p} /= ")" do -- \italic{p} is "," or "(" -- preprocess an argument expression \italic{p} := DoExpr(Deblank(end(\italic{p})), \italic{v}); -- now \italic{p} is the ")" -- remove the function name from the program text replace(\italic{id}, EMPTY); -- insert the function call before ")" return next(next(replace(start(\italic{p}), \italic{theCall}))); \}} In practice, the \keyword{while} loop contains an additional test for \italic{p}=";", which indicates that a right parenthesis has been omitted. This is fixed by inserting a right parenthesis and printing an error message. For strings of ASCII text, execution with the present implementation of the algebra is not as fast as with routines coded directly in C. The Ness preprocessor (567 lines) processes itself in under 35 seconds on a Sun 2/140. About a third of this time is taken because each marker variable is a pointer to a marker value rather than being a marker value itself. About ten percent of the time is occupied in moving strings around, which can be reduced by introducing an algroithm to apportion gap space among multiple gaps. Another ten percent of the time can be saved by recoding anyof() and span() to test bit vectors rather than call search() for every character. \heading{8. Experience} A number of working programs have been implemented utilizing the substring algebra in \ness{Ness} and CMU-Tutor. No major difficulties have been encountered and users have been universally enthusiastic about the ease of programming. Only time will tell whether this ease will carry over to a simplicity of maintenance. The largest program is the Ness compiler of which a sample was given in the previous Section. This program modifies the input file in memory to produce a corresponding C file which is output as a whole after the translation. To illustrate the ease of programming, the entire program had only three bugs. Modification and extension have continued with no new bugs being introduced. Another large program was written to study the feasibility of more general pattern matching in Ness. The program parses pattern expressions, converts them to a tree form, and interprets them by using them to find substrings in a text. (The tree form is generated with embedded C code.) The grammar implemented includes exact match, star for multiple instances, match any of a set of characters, and alternation of patterns. Other programs written in \ness{Ness} include an arithmetic expression parser and interpreter, conversions in both directions between roman numerals and decimal, permutations of characters and words, and counting the words in a file. Programs written in CMU-Tutor include \indent{Reverse a List Alphabetize a List Count Vowels in a Text Translate to Pig-Latin Plot Two User Functions Simultaneously Plot Parametric Equations} The last two of these exploit the CMU-Tutor run-time capability for compiling and executing mathematical statements. Thus the functions to be processed are typed in by the user, modified with the substring algebra, compiled, and plotted. \heading{9. Extensions and Open Questions} The substring algebra has so far been shown necessary and sufficient in a narrow sense, but many additional facilities can be proposed which are not easy to define with the primitives: \bold{inalphabet(< s1 [ c s2 ] s3 >) => < a1 [ c ] a2 >,} where < a1 c a2 > is one of the known alphabets. \indent{inalphabet(\italic{m}) returns a marker for a copy of the first letter of \italic{m}, but a copy within a string which is the entire alphabet for that character.} With inalphabet() as a primitive, all functions over alphabets can be computed. To give the "name" of an alphabet within a program it is sufficient to give a string containing a character from that alphabet. (This assumes that the editor used to create programs is capable of typing characters in any alphabet.) \bold{bound(< s1 [ s2 ] s3 >) => < [ s2 ] >.} \indent{Bound(\italic{m}) appears to have the same value as \italic{m}~"", but the implementation of bound() is such that the value is not copied and remains a piece of its original base string.} Bound() provides a means to restrict a pattern match to a substring of a base. \bold{readonly(< s1 [ s2 ] s3 >) => < s1 [ s2 ] s3 >}. \indent{The return value is a marker on the same base as the original argument, but marked as read only so it has the same behavior as a constant.} Readonly() permits passing a substring to a function and guaranteeing that the function does not modify the substring or its base. Other functions have been defined to manipulate the typographic styles of strings, but these are beyond the scope of this paper. An open question is whether a flag should be associated with each marker that would be set when the marked text was modified with a replace(). No use for this facility has occurred in examples to date, but it has been used within a text editor. Another open question is whether there should be some syntax for the substring functions other than named functions. Perhaps ^, *, +, and - for start(), base(), next(), and extent()? Considerable experimentation is needed before we are ready for this step. In the time being we must answer the question of whether the function names used above are acceptable. Should they be delimited in some way to distinguish them from other, client-defined functions?The definition of replace() specifies a particular behavior for other markers on the same base as the destination. This specification has some nice properties, such as a simple formal description, a simple textual description, and a simple implementation. In none of the examples considered so far has any other definition been found to be essential, but it is not known if this is the case for all applications. On a practical level, it is a common error to assign a constant to a variable and then append values to the variable with ~:=. This fails because ~:= fails when replace()ing the end of the constant. Since the program code looks innocuous, some means should be found to make it work. \heading{10. Summary} We began with the notion of a "practical" algebra as one on which to base a programming language data type and then discussed the problems of existing notations for strings (none of which is a one-sorted algebra). A new algebra was then introduced in Sections 2 and 5, based on the primitive operations of next() start(), base(), extent(), newbase(), and replace(). A number of theorems were proven demonstrating the power of the algebra and a number of algorithms were exhibited written in \ness{Ness}, a research language incorporating the algebra. There are certainly some disadvantages to the algebra. String manipulations will be slower than with unembellished C and systems programmer will not have detailed control over the character representations of data. Numerous advantages outweigh these disadvantages, however: \indent{ Convenience and Expressivity. The best measure of the felicity of this algebra for programming is the enthusiasm of the programmers who have used it for substantial tasks. They like the facts that string sizes need not be estimated, poritions of strings can be replaced, and integers are not used as subscripts. They found the pattern matching functions sufficient without resorting to non-standard flow-of-control constructions. Representation Independence. The algebra is suitable no matter whether characters are encoded with one, two, or more bytes. These details are hidden from the application programmer. Indeed, the algebra is not specific to character strings and can be used with any sequence of objects. Necessity and Sufficiency. Theorems above have demonstrated that the primitive functions are Necessary and Sufficient for substring computations, and moreover, the algebra provides Universal Computability, so \italic{any} function can be computed with substrings alone. Of more practical importance is that the primitives are a small set which can be easily taught and thoroughly understood. Efficiency. The algebra contributes to efficiency because strings do not have to be copied for substring computations and because the representation independence prevents the doubling in size of all character strings if the domain is to include more character values than can be encoded with a single byte. The algebra also contributes to efficiency in reduced programming and debugging time. } The algebra described above was originally motivated by the desire to deal with modern string values, possibly containing unusual characters or typography. After using it for some time, however, it seems to meet this goal and go far beyond, providing an excellent tool for general string processing. \bold{Acknowledgements.} Bruce Sherwood has been an unending source of enthusiasm and encouragement as well as the one who wanted the algebra as a tool for the CMU-Tutor system. I am indebted to him, Judy Sherwood, David Anderson and others at the Center for Design of Educational Computing, Carnegie-Mellon University, who have been implementing and exploring the algebra. This work would not have been possible without the generous support of the Department of Computer Science at the University of Glasgow, and the Science and Engineering Research Council (grant number GR/D89028), both under the energetic and stimulating direction of Malcolm Atkinson. The work has benefitted from conversations with Kieran Clenaghan, David Harper, Joe Morris, and John Launchberry. \majorheading{References} [Adobe, 1985] Adobe Systems, Inc., \italic{Postscript Language: Reference Manual,} Addison-Wesley, (Reading, Mass., 1985). [Alpert & Bitzer, 1970] Alpert, D., & D. L. Bitzer, \italic{Science} 167, 1582 (1970). [Farber, 1964] Farber, D. J., R. E. Griswold, I. P. Polonsky, "Snobol, a String Manipulation Language," \italic{J. ACM \italic{11}, }1 (1964) pp. 21-30. [Gimpel, 1976] Gimpel, J. F., \italic{Algorithms in SNOBOL4}, John Wiley & Sons (New York, 1976). [Griswold, 1979] Griswold, R. E., D. R. Hanson, and J. T. Korb, "The Icon Prgoramming Language: An Overview," \italic{SIGPLAN Notices 14}, 4 (April, 1979) 18-31. [Griswold, 1980] Griswold, R. E., and D. R. Hanson, "An Alternative to the Use of Patterns in String Processing," \italic{ACM TOPLAS}, 2, 2 (April, 1980) 153-172. [Hansen, 1987a] Hansen, W. J., \italic{\ness{Ness} - Reference Manual}, Computer Science Dept., Univ. of Glasgow, 1987. [Hansen, 1987b] Hansen, W. J., \italic{Em - Reference Manual}, Computer Science Dept., Univ. of Glasgow, 1987. [Hansen, 1987c] Hansen, W. J., Data Structures in a Bit-Mapped Text-Editor, \italic{Byte} (January, 1987). [McKeeman, 1970] McKeeman, W. M., J. J. Horning, and D. B. Wortman, \italic{A Compiler Generator,} Prentice-Hall, Inc. (Englewood Cliffs, 1970). [Morris, 1986] Morris, J., Satyarayanan, M., Conner, M. H., Howard, J. H., Rosenthal, D. S. H., Smith, F. D. "Andrew: A distributed Personal Computing Environment," \italic{Comm. ACM}, V. 29, 3 (March, 1986) 184-201. [Sherwood, 1977] Sherwood, B. A. \italic{The TUTOR Language,} Control Data Education Co. (Minneapolis, 1977). [Sherwood, 1986a] Sherwood, B. A., and J, N, Sherwood, \italic{The CMU-Tutor Language, Preliminary Edition}, Stipes Publishing Company (10 Chester Street, Champaign, Ill., 1986). [Sherwood, 1986b] Sherwood, J. N. \italic{CMU Tutor Reference Manual}. Center for Design of Educational Computing, Carnegie-Mellon University (Pittsburgh, 1986). (This is a printed version of the on-line reference manual.) \formatnote{ .bp } (a) \italic{n} \italic{m} \italic{p} < N o w - i s - t h e - t i m e - f o r - a l l > start(\italic{n}) start(\italic{m}) start(\italic{p}) next(\italic{n}) next(\italic{m}) next(\italic{p}) base(\italic{n}) base(\italic{m}) base(\italic{p}) (b) \italic{n} \italic{m} \italic{p} < N o w - i s - t h e - t i m e - f o r - a l l > extent(\italic{n}, \italic{m}) extent(\italic{m}, \italic{n}) extent(\italic{m}, \italic{p}) \bold{Figure 1. The four primitive functions.} The base string for all examples is the non-blank characters between < and > . The marked portion of non-empty markers is shown as an elongated H and that of empty markers as a headless up-arrow. \formatnote{ .bp } (a) A non-empty marker \italic{m} < A l l - m i m s y - w e r e - t h e - b o r o g o v e s > previous(\italic{m}) first(\italic{m}) rest(\italic{m}) end(\italic{m}) allprevious(\italic{m}) front(\italic{m}) last(\italic{m}) allnext(\italic{m}) (b) An empty marker \italic{n} < A l l - m i m s y - w e r e - t h e - b o r o g o v e s > first(\italic{n}) front(\italic{n}) rest(\italic{n}) last(\italic{n}) \bold{Figure 2. Some derived substring functions.} \formatnote{ .bp } (a) Before \italic{m n} < T h e - q u i c k - s i l v e r - b o x - j u m p e d > \italic{o q s p r t} (b) After replace(\italic{m}, "round-f") \italic{m s n} < T h e - q u i c k - r o u n d - f o x - j u m p e d > \italic{ o q p r t} \bold{Figure 3. The effect of a replace() on other markers.} \formatnote{ .bp }The style Ness has attributes: Font:AndySans The style keyword has attributes: Font:AndySans The style Region,Example has attributes: Enable: PassThru Mode: LeftFlush LeftMargin: 0.5i Insert some obscure character in the blank in third text paragraph of section 2. \enddata{text,269832672}