Chapter 11 Recursive Data Types Recursive data types play a central role in programming. From a mathematical point of view, recursive data types are what induction is about. Recursive data types are specified by recursive definitions that say how to build something from its parts. These definitions have two parts: • Base case(s) that don’t depend on anything else. • Constructor case(s) that depend on previous cases. 11.1 Strings of Brackets Let brkts be the set of all strings of square brackets. For example, the following two strings are in brkts: [ ] ] [ [ [ [ [ ] ] and [ [ [ ] ] [ ] ] [ ] (11.1) Since we’re just starting to study recursive data, just for practice we’ll formulate brkts as a recursive data type, Definition 11.1.1. The data type, brkts, of strings of brackets is defined recur-sively: • Base case: The empty string, λ, is in brkts. • Constructor case: If s ∈ brkts, then s] and s[ are in brkts. Here we’re writing s] to indicate the string that is the sequence of brackets (if any) in the string s, followed by a right bracket; similarly for s[ . A string, s ∈ brkts, is called a matched string if its brackets “match up” in the usual way. For example, the left hand string above is not matched because its second right bracket does not have a matching left bracket. The string on the right is matched. 207208 CHAPTER 11. RECURSIVE DATA TYPES We’re going to examine several different ways to define and prove properties of matched strings using recursively defined sets and functions. These properties are pretty straighforward, and you might wonder whether they have any partic-ular relevance in computer scientist —other than as a nonnumerical example of recursion. The honest answer is “not much relevance, any more.” The reason for this is one of the great successes of computer science. Expression Parsing During the early development of computer science in the 1950’s and 60’s, creation of effective programming language compilers was a central concern. A key aspect in processing a program for compilation was expression parsing. The problem was to take in an expression like x + y ∗ z 2 ÷ y + 7 and put in the brackets that determined how it should be evaluated —should it be [[x + y] ∗ z 2 ÷ y] + 7, or, x + [y ∗ z 2 ÷ [y + 7]], or, [x + [y ∗ z 2]] ÷ [y + 7], or . . . ? The Turing award (the “Nobel Prize” of computer science) was ultimately be-stowed on Robert Floyd, for, among other things, being discoverer of a simple program that would insert the brackets properly. In the 70’s and 80’s, this parsing technology was packaged into high-level compiler-compilers that automatically generated parsers from expression gram-mars. This automation of parsing was so effective that the subject needed no longer demanded attention. It largely disappeared from the computer science curriculum by the 1990’s. One precise way to determine if a string is matched is to start with 0 and read the string from left to right, adding 1 to the count for each left bracket and sub-tracting 1 from the count for each right bracket. For example, here are the counts11.1. STRINGS OF BRACKETS 209 for the two strings above [ ] ] [ [ [ [ [ ] ] ] ] 0 1 0 −1 0 1 2 3 4 3 2 1 0 [ [ [ ] ] [ ] ] [ ] 0 1 2 3 2 1 2 1 0 1 0 A string has a good count if its running count never goes negative and ends with 0. So the second string above has a good count, but the first one does not because its count went negative at the third step. Definition 11.1.2. Let GoodCount ::= {s ∈ brkts | s has a good count} . The matched strings can now be characterized precisely as this set of strings with good counts. But it turns out to be really useful to characterize the matched strings in another way as well, namely, as a recursive data type: Definition 11.1.3. Recursively define the set, RecMatch, of strings as follows: • Base case: λ ∈ RecMatch. • Constructor case: If s, t ∈ RecMatch, then [ s ] t ∈ RecMatch. Here we’re writing [ s ] t to indicate the string that starts with a left bracket, followed by the sequence of brackets (if any) in the string s, followed by a right bracket, and ending with the sequence of brackets in the string t. Using this definition, we can see that λ ∈ RecMatch by the Base case, so [ λ] λ = [ ] ∈ RecMatch by the Constructor case. So now, [ λ] [ ] = [ ] [ ] ∈ RecMatch (letting s = λ, t = [ ] ) [ [ ] ] λ = [ [ ] ] ∈ RecMatch (letting s = [ ] , t = λ) [ [ ] ] [ ] ∈ RecMatch (letting s = [ ] , t = [ ] ) are also strings in RecMatch by repeated applications of the Constructor case. If you haven’t seen this kind of definition before, you should try continuing this example to verify that [ [ [ ] ] [ ] ] [ ] ∈ RecMatch Given the way this section is set up, you might guess that RecMatch = GoodCount, and you’d be right, but it’s not completely obvious. The proof is worked out in Problem 11.6.210 CHAPTER 11. RECURSIVE DATA TYPES 11.2 Arithmetic Expressions Expression evaluation is a key feature of programming languages, and recognition of expressions as a recursive data type is a key to understanding how they can be processed. To illustrate this approach we’ll work with a toy example: arithmetic expres-sions like 3x2 + 2x + 1 involving only one variable, “x.” We’ll refer to the data type of such expressions as Aexp. Here is its definition: Definition 11.2.1. • Base cases: 1. The variable, x, is in Aexp. 2. The arabic numeral, k, for any nonnegative integer, k, is in Aexp. • Constructor cases: If e, f ∈ Aexp, then 3. (e + f) ∈ Aexp. The expression (e + f) is called a sum. The Aexp’s e and f are called the components of the sum; they’re also called the summands. 4. (e ∗ f) ∈ Aexp. The expression (e ∗ f ) is called a product. The Aexp’s e and f are called the components of the product; they’re also called the multiplier and multiplicand. 5. −(e) ∈ Aexp. The expression −(e) is called a negative. Notice that Aexp’s are fully parenthesized, and exponents aren’t allowed. So the Aexp version of the polynomial expression 3x2 + 2x + 1 would officially be written as ((3 ∗ (x ∗ x)) + ((2 ∗ x) + 1)). (11.2) These parentheses and ∗’s clutter up examples, so we’ll often use simpler expres-sions like “3x2 + 2x + 1” instead of (11.2). But it’s important
View Full Document
Unlocking...