diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/ssch23/vectors.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch23/vectors.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch23/vectors.html | 925 |
1 files changed, 925 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch23/vectors.html b/js/games/nluqo.github.io/~bh/ssch23/vectors.html new file mode 100644 index 0000000..9dc1c40 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch23/vectors.html @@ -0,0 +1,925 @@ +<P> + +<P><CENTER><IMG SRC="../ss-pics/lockers.jpg" ALT="figure: lockers"></CENTER><A NAME="lockers"></A><P><CENTER>A row of boxes +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 23: Vectors</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 23</H2> +<H1>Vectors</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../simply.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/ssch23.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../ssch22/files.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch24/spread.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT +Press web page for <CITE>Simply Scheme</CITE></A> +</TABLE></TABLE> + +<HR> + +<P>So far all the programs we've written in this book have had no memory of the +past history of the computation. We invoke a function with certain +arguments, and we get back a value that depends only on those arguments. +Compare this with the operation of Scheme itself: + +<P><PRE>> (foo 3) +ERROR: FOO HAS NO VALUE + +> (define (foo x) + (word x x)) + +> (foo 3) +33 +</PRE> + +<P>Scheme <EM>remembers</EM> that you have defined <CODE>foo</CODE>, so its response to +the very same expression is different the second time. Scheme maintains a +record of certain results of its past interaction with you; in particular, +Scheme remembers the global variables that you have defined. This record is +called its <EM>state.</EM> + +<P>Most of the programs that people use routinely are full of state; your text +editor, for example, remembers all the characters in your file. In this +chapter you will learn how to write programs with state. + +<P><H2>The Indy 500</H2> + +<P>The Indianapolis 500 is an annual 500-mile automobile race, famous among +people who like that sort of thing. It's held at the Indianapolis Motor +<A NAME="g1"></A> +Speedway, a racetrack in Indianapolis, Indiana. (Indiana is better known as +the home of Dan Friedman, the coauthor of some good books about Scheme.) +The racetrack is 2½ miles long, so, as you might imagine, the +racers have to complete 200 laps in order to finish the race. This means +that someone has to keep track of how many laps each car has completed so +far. + +<P>Let's write a program to help this person keep count. Each car has a +number, and the count person will invoke the procedure <CODE>lap</CODE> with that +number as argument every time a car completes a lap. The procedure will +return the number of laps that that car has completed altogether: + +<P><PRE>> (lap 87) +1 + +> (lap 64) +1 + +> (lap 17) +1 + +> (lap 64) +2 + +> (lap 64) +3 +</PRE> + +<P>(Car 64 managed to complete three laps before the other cars +completed two because the others had flat tires.) Note that we typed +the expression <CODE>(lap 64)</CODE> three times and got three different answers. +<CODE>Lap</CODE> isn't a function! A function has to return the same answer +whenever it's invoked with the same arguments. + +<P><H2>Vectors</H2> + +<P>The point of this chapter is to show how procedures like <CODE>lap</CODE> can be +written. To accomplish this, we're going to use a data structure called a +<EM>vector.</EM> (You may have seen something similar in other +programming languages under the name "array.") + +<P>A vector is, in effect, a row of boxes into which values can be put. Each +vector has a fixed number of boxes; when you create a vector, you have to say +how many boxes you want. Once a vector is created, there are two things you +can do with it: You can put a new value into a box (replacing any old value +that might have been there), or you can examine the value in a box. The +boxes are numbered, starting with zero. + +<P><PRE>> (define v (<A NAME="g2"></A>make-vector 5)) + +> (<A NAME="g3"></A>vector-set! v 0 'shoe) + +> (vector-set! v 3 'bread) + +> (vector-set! v 2 '(savoy truffle)) + +> (<A NAME="g4"></A>vector-ref v 3) +BREAD +</PRE> + +<P>There are several details to note here. When we invoke <CODE>make-vector</CODE> we +give it one argument, the number of boxes we want the vector to have. (In +this example, there are five boxes, numbered 0 through 4. There is no +box 5.) When we create the vector, there is nothing in any of the +boxes.<A NAME="text1" HREF="vectors.html#ft1">[1]</A> + +<P>We put things in boxes using the <CODE>vector-set!</CODE> procedure. The +exclamation point in its name, indicates that this is a <EM>mutator</EM>—a procedure that changes the value of some previously +created data structure. The exclamation point is pronounced "bang," as in +"vector set bang." (Scheme actually has several such mutators, including +mutators for lists, but this is the only one we'll use in this book. +A procedure that modifies its argument is also called <EM>destructive.</EM>) The arguments to <CODE>vector-set!</CODE> are the vector, the +number of the box (the <EM>index</EM>), and the desired new value. Like <CODE>define</CODE>, <CODE>vector-set!</CODE> returns an unspecified value. + +<P>We examine the contents of a box using <CODE>vector-ref</CODE>, which takes two +arguments, the vector and an index. <CODE>Vector-ref</CODE> is similar to <CODE>list-ref</CODE>, except that it operates on vectors instead of lists. + +<P>We can change the contents of a box that already has something in it. + +<P><PRE>> (vector-set! v 3 'jewel) + +> (vector-ref v 3) +JEWEL +</PRE> + +<P>The old value of box 3, <CODE>bread</CODE>, is no longer there. It's +been replaced by the new value. + +<P><PRE>> (vector-set! v 1 741) + +> (vector-set! v 4 #t) + +> v +#(SHOE 741 (SAVOY TRUFFLE) JEWEL #T) +</PRE> + +<P>Once the vector is completely full, we can print its value. Scheme +prints vectors in a format like that of lists, except that there is a number +sign (<CODE>#</CODE>) before the open parenthesis. If you ever have need for a +constant vector (one that you're not going to mutate), you can quote it +using the same notation: + +<P><PRE>> (vector-ref '#(a b c d) 2) +C +</PRE> + +<P><H2>Using Vectors in Programs</H2> + +<P>To implement our <CODE>lap</CODE> procedure, we'll keep its state information, the +lap counts, in a vector. We'll use the car number as the index into the +vector. It's not enough to create the vector; we have to make sure that +each box has a zero as its initial value. + +<P><PRE>(define *lap-vector* (make-vector 100)) + +(define (<A NAME="g5"></A>initialize-lap-vector index) + (if (< index 0) + 'done + (begin (vector-set! *lap-vector* index 0) + (initialize-lap-vector (- index 1))))) + +> (initialize-lap-vector 99) +DONE +</PRE> + +<P>We've created a global variable whose value is the vector. We +used a recursive procedure to put a zero into each box of the +vector.<A NAME="text2" HREF="vectors.html#ft2">[2]</A> Note that the +vector is of length 100, but its largest index is 99. Also, the base case +of the recursion is that the index is less than zero, not equal to zero as +in many earlier examples. That's because zero is a valid index. + +<P>Now that we have the vector, we can write <CODE>lap</CODE>. + +<P><PRE>(define (<A NAME="g6"></A>lap car-number) + (vector-set! *lap-vector* + car-number + (+ (vector-ref *lap-vector* car-number) 1)) + (vector-ref *lap-vector* car-number)) +</PRE> + +<P>Remember that a procedure body can include more than one +expression. When the procedure is invoked, the expressions will be +evaluated in order. The value returned by the procedure is the value of the +last expression (in this case, the second one). + +<P><CODE>Lap</CODE> has both a return value and a side effect. The job of the first +expression is to carry out that side effect, that is, to add 1 to the lap +count for the specified car. The second expression looks at the value we +just put in a box to determine the return value. + +<P><H2>Non-Functional Procedures and State</H2> + +<P>We remarked earlier that <CODE>lap</CODE> isn't a function because invoking it +twice with the same argument doesn't return the same value both +times.<A NAME="text3" HREF="vectors.html#ft3">[3]</A> + +<P>It's not a coincidence that <CODE>lap</CODE> also violates functional programming +by maintaining state information. Any procedure whose return value is not a +function of its arguments (that is, whose return value is not always the +same for any particular arguments) must depend on knowledge of what has +happened in the past. After all, computers don't pull results out of the +air; if the result of a computation doesn't depend entirely on the arguments +we give, then it must depend on some other information available to the +program. + +<P>Suppose somebody asks you, "Car 54 has just completed a lap; how many has it +completed in all?" You can't answer that question with only the information +in the question itself; you have to remember earlier events in the race. By +contrast, if someone asks you, "What's the plural of `book'?" what has +happened in the past doesn't matter at all. + +<P>The connection between non-functional procedures and state also applies to +non-functional Scheme primitives. The <CODE>read</CODE> procedure, for example, +returns different results when you invoke it repeatedly with the same +argument because it remembers how far it's gotten in the file. That's why +the argument is a port instead of a file name: A port is an abstract data +type that includes, among other things, this piece of state. (If you're +reading from the keyboard, the state is in the person doing the typing.) + +<P>A more surprising example is the <A NAME="g7"></A><CODE>random</CODE> procedure that you met in +Chapter 2. <CODE>Random</CODE> isn't a function because it doesn't always +return the same value when called with the same argument. How does <CODE>random</CODE> compute its result? Some versions of <CODE>random</CODE> compute a number +that's based on the current time (in tiny units like milliseconds so you +don't get the same answer from two calls in quick succession). How does +your computer know the time? Every so often some procedure (or some +hardware device) adds 1 to a remembered value, the number of milliseconds +since midnight. That's state, and <CODE>random</CODE> relies on it. + +<P>The most commonly used algorithm for random numbers is a little trickier; +each time you invoke <CODE>random</CODE>, the result is a function of <EM>the +result from the last time you invoked it.</EM> (The procedure is pretty +complicated; typically the old number is multiplied by some large, carefully +chosen constant, and only the middle digits of the product are kept.) Each +time you invoke <CODE>random</CODE>, the returned value is stashed away somehow so +that the next invocation can remember it. That's state too. + +<P>Just because a procedure remembers something doesn't necessarily make it +stateful. <EM>Every</EM> procedure remembers the arguments with which it was +invoked, while it's running. Otherwise the arguments wouldn't be able to +affect the computation. A procedure whose result depends only on its +arguments (the ones used in the current invocation) is functional. The +procedure is non-functional if it depends on something outside of its +current arguments. It's that sort of "long-term" memory that we consider +to be state. + +<P>In particular, a procedure that uses <CODE>let</CODE> isn't stateful merely because +the body of the <CODE>let</CODE> remembers the values of the variables created by the +<CODE>let</CODE>. Once <CODE>let</CODE> returns a value, the variables that it created no +longer exist. You couldn't use <CODE>let</CODE>, for example, to carry out the +kind of remembering that <CODE>random</CODE> needs. <CODE>Let</CODE> doesn't remember a +value <EM>between</EM> invocations, just during a single invocation. + +<P><H2>Shuffling a Deck</H2> + +<P>One of the advantages of the vector data structure is that it allows +elements to be rearranged. As an example, we'll create and shuffle a +deck of cards. + +<P>We'll start with a procedure <CODE>card-list</CODE> that returns a list of all the +cards, in standard order: + +<P><PRE>(define (<A NAME="g8"></A>card-list) + (reduce append + (map (lambda (suit) (map (lambda (rank) (word suit rank)) + '(a 2 3 4 5 6 7 8 9 10 j q k))) + '(h s d c)))) + +> (card-list) +(HA H2 H3 H4 H5 H6 H7 H8 H9 H10 HJ HQ HK + SA S2 S3 S4 S5 S6 S7 S8 S9 S10 SJ SQ SK + DA D2 D3 D4 D5 D6 D7 D8 D9 D10 DJ DQ DK + CA C2 C3 C4 C5 C6 C7 C8 C9 C10 CJ CQ CK) +</PRE> + +<P>In writing <CODE>card-list</CODE>, we need <CODE>reduce append</CODE> because the result +from the outer invocation of <CODE>map</CODE> is a list of lists: <CODE>((HA H2 …) (SA …) …)</CODE>.<A NAME="text4" HREF="vectors.html#ft4">[4]</A> + +<P>Each time we want a new deck of cards, we start with this list of 52 cards, +copy the list into a vector, and shuffle that vector. We'll use the Scheme +primitive <CODE><A NAME="g9"></A><CODE>list->vector</CODE></CODE>, which takes a list as argument and +returns a vector of the same length, with the boxes initialized to the +corresponding elements of the list. (There is also a procedure <CODE><A NAME="g10"></A><CODE>vector->list</CODE></CODE> that does the reverse. The characters <CODE>-></CODE> in +these function names are meant to look like an arrow +(→); this is a Scheme convention for functions +that convert information from one data type to another.) + +<P><PRE>(define (<A NAME="g11"></A>make-deck) + (shuffle! (list->vector (card-list)) 51)) + +(define (<A NAME="g12"></A>shuffle! deck index) + (if (< index 0) + deck + (begin (vector-swap! deck index (random (+ index 1))) + (shuffle! deck (- index 1))))) + +(define (<A NAME="g13"></A>vector-swap! vector index1 index2) + (let ((temp (vector-ref vector index1))) + (vector-set! vector index1 (vector-ref vector index2)) + (vector-set! vector index2 temp))) +</PRE> + +<P> +<P>Now, each time we call <CODE>make-deck</CODE>, we get a randomly shuffled +vector of cards: + +<P><PRE>> (make-deck) +#(C4 SA C7 DA S4 D9 SQ H4 C10 D5 H9 S10 D6 + S9 CA C9 S2 H7 S5 H6 D7 HK S7 C3 C2 C6 + HJ SK CQ CJ D4 SJ D8 S8 HA C5 DK D3 HQ + D10 H8 DJ C8 H2 H5 H3 CK S3 DQ S6 D2 H10) + +> (make-deck) +#(CQ H7 D10 D5 S8 C7 H10 SQ H4 H3 D8 C9 S7 + SK DK S6 DA D4 C6 HQ D6 S2 H5 CA H2 HJ + CK D7 H6 HA CJ C4 SJ HK SA C2 D2 S4 DQ + S5 C10 H9 D9 C5 D3 DJ C3 S9 S3 C8 S10 H8) +</PRE> + +<P>How does the shuffling algorithm work? Conceptually it's not complicated, +but there are some implementation details that make the actual procedures a +little tricky. The general idea is this: We want all the cards shuffled +into a random order. So we choose any card at random, and make it the first +card. We're then left with a one-card-smaller deck to shuffle, and we do +that by recursion. (This algorithm is similar to selection sort from +Chapter 15, except that we select a random card each time instead of +selecting the smallest value.) + +<P>The details that complicate this algorithm have to do with the fact that +we're using a vector, in which it's easy to change the value in one +particular position, but it's not easy to do what would otherwise be the +most natural thing: If you had a handful of actual cards and wanted to move +one of them to the front, you'd slide the other cards over to make room. +There's no "sliding over" in a vector. Instead we use a trick; we happen +to have an empty slot, the one from which we removed the randomly chosen +card, so instead of moving several cards, we just move the one card that was +originally at the front into that slot. In other words, we exchange two +cards, the randomly chosen one and the one that used to be in front. + +<P>Second, there's nothing comparable to <CODE>cdr</CODE> to provide a +one-card-smaller vector to the recursive invocation. Instead, we must use +the entire vector and also provide an additional <CODE>index</CODE> argument, a +number that keeps track of how many cards remain to be shuffled. It's +simplest if each recursive invocation is responsible for the range of cards +from position <CODE>0</CODE> to position <CODE>index</CODE> of the vector, and therefore +the program actually moves each randomly selected card to the <EM>end</EM> of +the remaining portion of the deck. + +<P><H2>More Vector Tools</H2> + +<P>If you want to make a vector with only a few boxes, and you know in advance +what values you want in those boxes, you can use the constructor +<A NAME="g14"></A><CODE>vector</CODE>. Like <CODE>list</CODE>, it takes any number of arguments and +returns a vector containing those arguments as elements: + +<P><PRE>> (define beatles (vector 'john 'paul 'george 'pete)) + +> (vector-set! beatles 3 'ringo) + +> beatles +#(JOHN PAUL GEORGE RINGO) +</PRE> + +<P>The procedure <A NAME="g15"></A><CODE>vector-length</CODE> takes a vector as argument and returns the +number of boxes in the vector. + +<P><PRE>> (vector-length beatles) +4 +</PRE> + +<P>The predicate <CODE>equal?</CODE>, which we've used with words and lists, also +accepts vectors as arguments. Two vectors are equal if they are the same +size and all their corresponding elements are equal. (A list and a vector +are never equal, even if their elements are equal.) + +<P>Finally, the predicate <A NAME="g16"></A><CODE>vector?</CODE> takes anything as argument and returns +<CODE>#t</CODE> if and only if its argument is a vector. + +<P><H2>The Vector Pattern of Recursion</H2> + +<P>Here are two procedures that you've seen earlier in this chapter, which do +something to each element of a vector: + +<P><PRE>(define (initialize-lap-vector index) + (if (< index 0) + 'done + (begin (vector-set! *lap-vector* index 0) + (initialize-lap-vector (- index 1))))) + +(define (shuffle! deck index) + (if (< index 0) + deck + (begin (vector-swap! deck index (random (+ index 1))) + (shuffle! deck (- index 1))))) +</PRE> + +<P>These procedures have a similar structure, like the similarities we found in +other recursive patterns. Both of these procedures take an index as an +argument, and both have + +<P><PRE>(< index 0) +</PRE> + +<P>as their base case. Also, both have, as their recursive case, a +<CODE>begin</CODE> in which the first action does something to the vector element +selected by the current index, and the second action is a recursive call +with the index decreased by one. These procedures are initially called with +the largest possible index value. + +<P>In some cases it's more convenient to count the index upward from zero: + +<P><PRE>(define (<A NAME="g17"></A>list->vector lst) + (l->v-helper (make-vector (length lst)) lst 0)) + +(define (l->v-helper vec lst index) + (if (= index (vector-length vec)) + vec + (begin (vector-set! vec index (car lst)) + (l->v-helper vec (cdr lst) (+ index 1))))) +</PRE> + +<P>Since lists are naturally processed from left to right (using +<CODE>car</CODE> and <CODE>cdr</CODE>), this program must process the vector from left to +right also. + +<P><H2>Vectors versus Lists</H2> + +<P>Since we introduced vectors to provide mutability, you may have the +impression that mutability is the main difference between vectors and +lists. Actually, lists are mutable too, although the issues are more +complicated; that's why we haven't used list mutation in this book. + +<P>The most important difference between lists and vectors is that each +kind of aggregate lends itself to a different style of programming, because +some operations are faster than others in each. List programming is +characterized by two operations: dividing a list into its first element and +all the rest, and sticking one new element onto the front of a list. Vector +programming is characterized by selecting elements in any order, from a +collection whose size is set permanently when the vector is created. + +<P>To make these rather vague descriptions more concrete, here are two +procedures, one of which squares every number in a list, and the other of +which squares every number in a vector: + +<P><PRE>(define (list-square numbers) + (if (null? numbers) + '() + (cons (square (car numbers)) + (list-square (cdr numbers))))) + +(define (vector-square numbers) + (vec-sq-helper (make-vector (vector-length numbers)) + numbers + (- (vector-length numbers) 1))) + +(define (vec-sq-helper new old index) + (if (< index 0) + new + (begin (vector-set! new index (square (vector-ref old index))) + (vec-sq-helper new old (- index 1))))) +</PRE> + +<P>In the list version, the intermediate stages of the algorithm +deal with lists that are smaller than the original argument. Each recursive +invocation "strips off" one element of its argument and "glues on" one +extra element in its return value. In the vector version, the returned +vector is created, at full size, as the first step in the algorithm; its +component parts are filled in as the program proceeds. + +<P>This example can plausibly be done with either vectors or lists, so we've +used it to compare the two techniques. But some algorithms fit most +naturally with one kind of aggregate and would be awkward and slow using +the other kind. The swapping of pairs of elements in the shuffling +algorithm would be much harder using lists, while mergesort would be harder +using vectors. + +<P>The best way to understand these differences in style is to know the +operations that are most efficient for each kind of aggregate. In each +case, there are certain operations that can be done in one small unit of +time, regardless of the number of elements in the aggregate, while other +operations take more time for more elements. The <EM>constant time</EM> +operations for lists are <CODE>cons</CODE>, <CODE>car</CODE>, <CODE>cdr</CODE>, and <CODE>null?</CODE>; +the ones for vectors are <CODE>vector-ref</CODE>, <CODE>vector-set!</CODE>, and <CODE>vector-length</CODE>.<A NAME="text5" HREF="vectors.html#ft5">[5]</A> And if you reread the +squaring programs, you'll find that these are precisely the operations +they use. + +<P>We might have used <CODE>list-ref</CODE> in the list version, but we didn't, and +Scheme programmers usually don't, because we know that it would be slower. +Similarly, we could implement something like <CODE>cdr</CODE> for vectors, but that +would be slow, too, since it would have to make a one-smaller vector and +copy the elements one at a time. There are two possible morals to this +story, and they're both true: First, programmers invent and learn the +algorithms that make sense for whatever data structure is available. Thus +we have well-known programming patterns, such as the <CODE>filter</CODE> pattern, +appropriate for lists, and different patterns appropriate for vectors. +Second, programmers choose which data structure to use depending on what +algorithms they need. If you want to shuffle cards, use a vector, but if +you want to split the deck into a bunch of variable-size piles, lists might +be more appropriate. In general, vectors are good at selecting elements in +arbitrary order from a fixed-size collection; lists are good only at +selecting elements strictly from left to right, but they can vary in size. + +<P>In this book, despite what we're saying here about efficiency, we've +generally tried to present algorithms in the way that's easiest to +understand, even when we know that there's a faster way. For example, we've +shown several recursive procedures in which the base case test was + +<P><PRE>(= (count sent) 1) +</PRE> + +<P>If we were writing the program for practical use, rather than for +a book, we would have written + +<P><PRE>(empty? (butfirst sent)) +</PRE> + +<P>because we know that <CODE>empty?</CODE> and <CODE>butfirst</CODE> are both +constant time operations (because for sentences they're implemented as +<CODE>null?</CODE> and <CODE>cdr</CODE>), while <CODE>count</CODE> takes a long time for large +sentences. But the version using <CODE>count</CODE> makes the intent +clearer.<A NAME="text6" HREF="vectors.html#ft6">[6]</A> + +<P><H2>State, Sequence, and Effects</H2> + +<P>Effects, sequence, and state are three sides of the same +coin.<A NAME="text7" HREF="vectors.html#ft7">[7]</A> + +<P>In Chapter 20 we explained the connection between effect (printing +something on the screen) and sequence: It matters what you print first. +We also noted that there's no benefit to a sequence of expressions unless +those expressions produce an effect, since the values returned by all but +the last expression are discarded. + +<P>In this chapter we've seen another connection. The way our vector programs +maintain state information is by carrying out effects, namely, <CODE>vector-set!</CODE> invocations. Actually, <EM>every</EM> effect changes some kind +of state; if not in Scheme's memory, then on the computer screen or in a +file. + +<P>The final connection to be made is between state and sequence. Once a +program maintains state, it matters whether some computation is carried out +before or after another computation that changes the state. The example at +the beginning of this chapter in which an expression had different results +before and after defining a variable illustrates this point. As another +example, if we evaluate <CODE>(lap 1)</CODE> 200 times and <CODE>(lap 2)</CODE> 200 times, +the program's determination of the winner of the race depends on whether the +last evaluation of <CODE>(lap 1)</CODE> comes before or after the last invocation +of <CODE>(lap 2)</CODE>. + +<P>Because these three ideas are so closely connected, the names <EM>sequential programming</EM> (emphasizing sequence) and <EM><A NAME="g18"></A><A NAME="g19"></A>imperative programming</EM> (emphasizing effect) are both used to +refer to a style of programming that uses all three. This style is in +contrast with functional programming, which, as you know, uses none of them. + +<P>Although functional and sequential programming are, in a sense, opposites, +it's perfectly possible to use both styles within one program, as we pointed +out in the tic-tac-toe program of Chapter 20. We'll show more such hybrid +programs in the following chapters. + +<P><H2>Pitfalls</H2> + +<P>Don't forget that the first element of a vector is number zero, and +there is no element whose index number is equal to the length of the +vector. (Although these points are equally true for lists, it doesn't often +matter, because we rarely select the elements of a list by number.) In +particular, in a vector recursion, if zero is the base case, then there's +probably still one element left to process. + +<P>Try the following experiment: + +<P><PRE>> (define dessert (vector 'chocolate 'sundae)) +> (define two-desserts (list dessert dessert)) +> (vector-set! (car two-desserts) 1 'shake) +> two-desserts +(#(CHOCOLATE SHAKE) #(CHOCOLATE SHAKE)) +</PRE> + +<P>You might have expected that after asking to change one word in +<CODE>two-desserts</CODE>, the result would be + +<P><PRE>(#(CHOCOLATE SHAKE) #(CHOCOLATE SUNDAE)) +</PRE> + +<P>However, because of the way we created <CODE>two-desserts</CODE>, both of +its elements are the <EM>same</EM> vector. If you think of a list as a +collection of things, it's strange to imagine the very same thing in two +different places, but that's the situation. If you want to have two separate +vectors that happen to have the same values in their elements, but are +individually mutable, you'd have to say + +<P><PRE>> (define two-desserts (list (vector 'chocolate 'sundae) + (vector 'chocolate 'sundae))) +> (vector-set! (car two-desserts) 1 'shake) +> two-desserts +(#(CHOCOLATE SHAKE) #(CHOCOLATE SUNDAE)) +</PRE> + +<P>Each invocation of <CODE>vector</CODE> or <CODE>make-vector</CODE> creates a +new, independent vector. + +<P><H2>Exercises</H2> + +<P> + +<P><EM>Do not solve any of the following exercises by converting a +vector to a list, using list procedures, and then converting the result back +to a vector.</EM> + +<P><B>23.1</B> Write a procedure <CODE><A NAME="g20"></A>sum-vector</CODE> that takes a vector full of +numbers as its argument and returns the sum of all the numbers: + +<P><PRE>> (sum-vector '#(6 7 8)) +21 +</PRE> + + +<P> +<B>23.2</B> Some versions of Scheme provide a procedure <A NAME="g21"></A><CODE>vector-fill!</CODE> that takes a +vector and anything as its two arguments. It replaces every element of the +vector with the second argument, like this: + +<P><PRE>> (define vec (vector 'one 'two 'three 'four)) + +> vec +#(one two three four) + +> (<A NAME="g22"></A>vector-fill! vec 'yeah) + +> vec +#(yeah yeah yeah yeah) +</PRE> + +<P>Write <CODE>vector-fill!</CODE>. (It doesn't matter what value it +returns.) + + +<P> +<B>23.3</B> Write a function <CODE><A NAME="g23"></A>vector-append</CODE> that works just like regular <CODE>append</CODE>, but for vectors: + +<P><PRE>> (vector-append '#(not a) '#(second time)) +#(not a second time) +</PRE> + + +<P> +<B>23.4</B> Write <CODE>vector->list</CODE>. + + +<P> +<B>23.5</B> Write a procedure <CODE><A NAME="g24"></A>vector-map</CODE> that takes two arguments, a +function and a vector, and returns a new vector in which each box contains +the result of applying the function to the corresponding element of the +argument vector. + + +<P> +<B>23.6</B> Write a procedure <CODE><A NAME="g25"></A>vector-map!</CODE> that takes two arguments, a +function and a vector, and modifies the argument vector by replacing each +element with the result of applying the function to that element. Your +procedure should return the same vector. + + +<P> +<B>23.7</B> Could you write <CODE>vector-filter</CODE>? How about <CODE>vector-filter!</CODE>? +Explain the issues involved. + + +<P> +<B>23.8</B> Modify the <CODE>lap</CODE> procedure to print "Car 34 wins!" when car 34 +completes its 200th lap. (A harder but more correct modification is +to print the message only if no other car has completed 200 laps.) + + +<P> +<B>23.9</B> <A NAME="itstrivial"></A> +Write a procedure <CODE><A NAME="g26"></A>leader</CODE> that says which car is in the lead +right now. + + +<P> +<B>23.10</B> Why doesn't this solution to Exercise <A HREF="vectors.html#itstrivial">23.9</A> work? + +<P><PRE>(define (leader) + (leader-helper 0 1)) + +(define (leader-helper leader index) + (cond ((= index 100) leader) + ((> (lap index) (lap leader)) + (leader-helper index (+ index 1))) + (else (leader-helper leader (+ index 1))))) +</PRE> + + +<P> +<B>23.11</B> In some restaurants, the servers use computer terminals to keep track of +what each table has ordered. Every time you order more food, the server +enters your order into the computer. When you're ready for the check, the +computer prints your bill. + +<P>You're going to write two procedures, <CODE><A NAME="g27"></A>order</CODE> and <CODE><A NAME="g28"></A>bill.</CODE> <CODE>Order</CODE> takes a table number and an item as arguments and +adds the cost of that item to that table's bill. <CODE>Bill</CODE> takes a table +number as its argument, returns the amount owed by that table, and resets +the table for the next customers. (Your <CODE>order</CODE> procedure can examine a +global variable <CODE>*menu*</CODE> to find the price of each item.) + +<P><PRE>> (order 3 'potstickers) + +> (order 3 'wor-won-ton) + +> (order 5 'egg-rolls) + +> (order 3 'shin-shin-special-prawns) + +> (bill 3) +13.85 + +> (bill 5) +2.75 +</PRE> + + +<P> +<B>23.12</B> Rewrite selection sort (from Chapter 15) to sort a vector. This can +be done in a way similar to the procedure for shuffling a deck: Find +the smallest element of the vector and exchange it (using <CODE>vector-swap!</CODE>) with the value in the first box. Then find the smallest +element not including the first box, and exchange that with the second box, +and so on. For example, suppose we have a vector of numbers: + +<P><PRE>#(23 4 18 7 95 60) +</PRE> + +<P>Your program should transform the vector through these +intermediate stages: + +<P><PRE>#(4 23 18 7 95 60) ; exchange 4 with 23 +#(4 7 18 23 95 60) ; exchange 7 with 23 +#(4 7 18 23 95 60) ; exchange 18 with itself +#(4 7 18 23 95 60) ; exchange 23 with itself +#(4 7 18 23 60 95) ; exchange 60 with 95 +</PRE> + + +<P> +<B>23.13</B> Why doesn't this work? + +<P><PRE>(define (vector-swap! vector index1 index2) + (vector-set! vector index1 (vector-ref vector index2)) + (vector-set! vector index2 (vector-ref vector index1))) +</PRE> + + +<P> +<B>23.14</B> Implement a two-dimensional version of vectors. (We'll call one of these +structures a <EM>matrix.</EM>) The implementation will use a vector of +vectors. For example, a three-by-five matrix will be a three-element +vector, in which each of the elements is a five-element vector. Here's +how it should work: +<A NAME="twodimvect"></A> + +<P><PRE>> (define m (make-matrix 3 5)) + +> (matrix-set! m 2 1 '(her majesty)) + +> (matrix-ref m 2 1) +(HER MAJESTY) +</PRE> + +<P> +<B>23.15</B> Generalize Exercise <A HREF="vectors.html#twodimvect">23.14</A> by implementing an <EM>array</EM> +structure that can have any number of dimensions. Instead of taking two +numbers as index arguments, as the matrix procedures do, the array +procedures will take one argument, a <EM>list</EM> of numbers. The number of +numbers is the number of dimensions, and it will be constant for any particular +array. For example, here is a three-dimensional array (4×5×6): +<A NAME="arrays"></A> + +<P><PRE>> (define a1 (make-array '(4 5 6))) + +> (array-set! a1 '(3 2 3) '(the end)) +</PRE> + +<P> +<B>23.16</B> We want to reimplement sentences as vectors instead of lists. + +<P>(a) Write versions of <CODE>sentence</CODE>, <CODE>empty?</CODE>, <CODE>first</CODE>, +<CODE>butfirst</CODE>, <CODE>last</CODE>, and <CODE>butlast</CODE> that use vectors. Your +selectors need only work for sentences, not for words. + +<P><PRE>> (sentence 'a 'b 'c) +#(A B C) + +> (butfirst (sentence 'a 'b 'c)) +#(B C) +</PRE> + +<P>(You don't have to make these procedures work on lists as well as +vectors!) + +<P>(b) Does the following program still work with the new +implementation of sentences? If not, fix the program. + +<P><PRE>(define (praise stuff) + (sentence stuff '(is good))) +</PRE> + +<P>(c) Does the following program still work with the new +implementation of sentences? If not, fix the program. + +<P><PRE>(define (praise stuff) + (sentence stuff 'rules!)) +</PRE> + +<P>(d) Does the following program still work with the new +implementation of sentences? If not, fix the program. If so, is there some +optional rewriting that would improve its performance? + +<P><PRE>(define (item n sent) + (if (= n 1) + (first sent) + (item (- n 1) (butfirst sent)))) +</PRE> + +<P> +<P>(e) Does the following program still work with the new +implementation of sentences? If not, fix the program. If so, is there some +optional rewriting that would improve its performance? + +<P><PRE>(define (every fn sent) + (if (empty? sent) + sent + (sentence (fn (first sent)) + (every fn (butfirst sent))))) +</PRE> + +<P>(f) In what ways does using vectors to implement sentences affect +the speed of the selectors and constructor? Why do you think we chose to +use lists? + + +<P> + +<HR> +<A NAME="ft1" HREF="vectors.html#text1">[1]</A> The Scheme standard says that the initial contents of the +boxes is "unspecified." That means that the result depends on the +particular version of Scheme you're using. It's a bad idea to try to +examine the contents of a box before putting something in it.<P> +<A NAME="ft2" HREF="vectors.html#text2">[2]</A> In some versions of Scheme, <CODE>make-vector</CODE> can take an +optional argument specifying an initial value to put in every box. In those +versions, we could just say + +<P><PRE>(define *lap-vector* (make-vector 100 0)) +</PRE> + +<P>without having to use the initialization procedure.<P> +<A NAME="ft3" HREF="vectors.html#text3">[3]</A> That's what we mean by "non-functional," not that it doesn't +work!<P> +<A NAME="ft4" HREF="vectors.html#text4">[4]</A> We could get around +this problem in a different way: + +<P><PRE>(define (card-list) + (every (lambda (suit) (every (lambda (rank) (word suit rank)) + '(a 2 3 4 5 6 7 8 9 10 j q k))) + '(h s d c))) +</PRE> + +<P>In this version, we're taking advantage of the fact that our +sentence data type was defined in a way that prevents the creation of +sublists. A sentence of cards is a good representation for the deck. +However, with this approach we are mixing up the list and sentence data +types, because later we're going to invoke <CODE>list->vector</CODE> with this deck +of cards as its argument. If we use sentence tools such as <CODE>every</CODE> to +create the deck, then the procedure <CODE>card-list</CODE> should really be called +<CODE>card-sentence</CODE>. + +<P>What difference does it make? The <CODE>every</CODE> version works fine, as long +as sentences are implemented as lists, so that <CODE>list->vector</CODE> can be +applied to a sentence. But the point about abstract data types such as +sentences is to avoid making assumptions about their implementation. If +for some reason we decided to change the internal representation of +sentences, then <CODE>list->vector</CODE> could no longer be applied to a sentence. +Strictly speaking, if we're going to use this trick, we need a separate +conversion procedure <CODE>sentence->vector</CODE>. + +<P>Of course, if you don't mind a little typing, you can avoid this whole issue +by having a quoted list of all 52 cards built into the definition of <CODE>card-list</CODE>. +<P> +<A NAME="ft5" HREF="vectors.html#text5">[5]</A> Where did this information come from? Just take our +word for it. In later courses you'll study how vectors and lists are +implemented, and then there will be reasons.<P> +<A NAME="ft6" HREF="vectors.html#text6">[6]</A> For words, it turns out, the <CODE>count</CODE> version is faster, +because words behave more like vectors than like lists.<P> +<A NAME="ft7" HREF="vectors.html#text7">[7]</A> … to coin a phrase.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch22/files.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch24/spread.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |