New version page

Vectors

Upgrade to remove ads

This preview shows page 1-2-19-20 out of 20 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

A row of boxesfoo23 VectorsThe Indy 500remembersstate.405>(foo 3)ERROR: FOO HAS NO VALUE>(define(foo x)(word x x))>(foo 3)33So far all the programs we’ve written in this book have had no memory of the past historyof the computation. We invoke a function with certain arguments, and we get back avalue that depends only on those arguments. Compare this with the operation of Schemeitself:Scheme that you have defined , so its response to the very sameexpression is different the second time. Scheme maintains a record of certain results ofits past interaction with you; in particular, Scheme remembers the global variables thatyou have defined. This record is called itsMost of the programs that people use routinely are full of state; your text editor, forexample, remembers all the characters in your file. In this chapter you will learn how towrite programs with state.The Indianapolis 500 is an annual 500-mile automobile race, famous among peoplewho like that sort of thing. It’s held at the Indianapolis Motor Speedway, a racetrackin Indianapolis, Indiana. (Indiana is better known as the home of Dan Friedman, the12Vectorslap(lap 64)Laplapvector.406 Part VI Sequential Programming>(lap 87)1>(lap 64)1>(lap 17)1>(lap 64)2>(lap 64)3>(define v(make-vector 5))coauthor of some good books about Scheme.) The racetrack is 2 miles long, so, as youmight imagine, the racers have to complete 200 laps in order to finish the race. Thismeans that someone has to keep track of how many laps each car has completed so far.Let’s write a program to help this person keep count. Each car has a number, andthe count person will invoke the procedure with that number as argument everytime a car completes a lap. The procedure will return the number of laps that that carhas completed altogether:(Car 64 managed to complete three laps before the other cars completed two becausethe others had flat tires.) Note that we typed the expression three times andgot three different answers. isn’t a function! A function has to return the sameanswer whenever it’s invoked with the same arguments.The point of this chapter is to show how procedures like can be written. Toaccomplish this, we’re going to use a data structure called a (You may have seensomething similar in other programming languages under the name “array.”)A vector is, in effect, a row of boxes into which values can be put. Each vector has afixed number of boxes; when you create a vector, you have to say how many boxes youwant. Once a vector is created, there are two things you can do with it: You can put anew value into a box (replacing any old value that might have been there), or you canexamine the value in a box. The boxes are numbered, starting with zero.mutatordestructive.indexChapter 23 Vectors 407make-vectorvector-set!vector-set!define vector-set!vector-refVector-ref list-refbread>(vector-set! v 0 ’shoe)>(vector-set! v 3 ’bread)>(vector-set! v 2 ’(savoy truffle))>(vector-ref v 3)BREAD>(vector-set! v 3 ’jewel)>(vector-ref v 3)JEWEL>(vector-set! v 1 741)* The Scheme standard says that the initial contents of the boxes is “unspecified.” That meansthat the result depends on the particular version of Scheme you’re using. It’s a bad idea to tr y toexamine the contents of a box before putting something in it.There are several details to note here. When we invoke we give itone argument, the number of boxes we want the vector to have. (In this example, thereare five boxes, numbered 0 through 4. There is no box 5.) When we create the vector,there is nothing in any of the boxes.*We put things in boxes using the procedure. The exclamation pointin its name, indicates that this is a —a procedure that changes the value of somepreviously created data structure. The exclamation point is pronounced “bang,” as in“vector set bang.” (Scheme actually has several such mutators, including mutators forlists, but this is the only one we’ll use in this book. A procedure that modifies its argumentis also called ) The arguments to are the vector, the number ofthe box (the ), and the desired new value. Like , returns anunspecified value.We examine the contents of a box using , which takes two arguments,the vector and an index. is similar to , except that it operateson vectors instead of lists.We can change the contents of a box that already has something in it.The old value of box 3, , is no longer there. It’s been replaced by the new value.#lapUsing Vectors in Programs408 Part VI Sequential Programming(define*lap-vector*(make-vector 100 0))* In some versions of Scheme, can take an optional argument specifying aninitial value to put in every box. In those versions, we could just saywithout having to use the initialization procedure.>(vector-set! v 4 #t)> v#(SHOE 741(SAVOY TRUFFLE)JEWEL #T)>(vector-ref ’#(a b c d)2)C(define*lap-vector*(make-vector 100))(define(initialize-lap-vector index)(if(< index 0)’done(begin(vector-set!*lap-vector*index 0)(initialize-lap-vector(-index 1)))))>(initialize-lap-vector 99)DONEmake-vectorOnce the vector is completely full, we can print its value. Scheme prints vectors in a formatlike that of lists, except that there is a number sign ( ) before the open parenthesis. Ifyou ever have need for a constant vector (one that you’re not going to mutate), you canquote it using the same notation:To implement our procedure, we’ll keep its state information, the lap counts, in avector. We’ll use the car number as the index into the vector. It’s not enough to createthe vector; we have to make sure that each box has a zero as its initial value.We’ve created a global variable whose value is the vector. We used a recursive procedureto put a zero into each box of the vector.* Note that the vector is of length 100, but itslargest 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.lapLaplaplapreadChapter 23 Vectors 409Non-Functional Procedures and State* That’s what we mean by “non-functional,” not that it doesn’t work!(define(lap car-number)(vector-set!*lap-vector*car-number(+(vector-ref*lap-vector*car-number)1))(vector-ref*lap-vector*car-number))Now that we have the vector, we can write .Remember that a procedure body can include more than one expression. When theprocedure is invoked, the expressions will be evaluated in order. The value returned bythe procedure is the value of the last


Download Vectors
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Vectors and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Vectors 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?