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/ssch7/variables.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch7/variables.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch7/variables.html | 505 |
1 files changed, 505 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch7/variables.html b/js/games/nluqo.github.io/~bh/ssch7/variables.html new file mode 100644 index 0000000..9c09572 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch7/variables.html @@ -0,0 +1,505 @@ +<P> + +<P><A NAME="trombone"></A><CENTER><IMG SRC="../ss-pics/trombone.jpg" ALT="figure: trombone"></CENTER><P><CENTER>Trombone players produce different pitches partly +by varying the length of a tube. +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 7: Variables</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 7</H2> +<H1>Variables</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/ssch07.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="../ssch6/true.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch8/part3.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>A <EM>variable</EM> is a connection between a name and a +<A NAME="g1"></A> value.<A NAME="text1" HREF="variables.html#ft1">[1]</A> That +sounds simple enough, but some complexities arise in practice. To avoid +confusion later, we'll spend some time now looking at the idea of +"variable" in more detail. + +<P>The name <EM>variable</EM> comes from algebra. Many people are introduced to +variables in high school algebra classes, where the emphasis is on solving +equations. "If <EM>x</EM><SUP>3</SUP>−8=0, what is the value of <EM>x</EM>?" In +problems like these, although we call <EM>x</EM> a variable, it's really a <EM><A NAME="g2"></A><A NAME="g3"></A>named constant!</EM> In this particular problem, <EM>x</EM> has the +value 2. In any such problem, at first we don't know the value of <EM>x</EM>, but +we understand that it does have some particular value, and that value isn't +going to change in the middle of the problem. + +<P>In functional programming, what we mean by "variable" is like a named +constant in mathematics. Since a variable is the connection between a name +and a value, a formal parameter in a procedure definition isn't a variable; +it's just a name. But when we invoke the procedure with a particular +argument, that name is associated with a value, and a variable is created. +If we invoke the procedure again, a <EM>new</EM> variable is created, perhaps +with a different value. + +<P>There are two possible sources of confusion about this. One is that you may +have programmed before in a programming language like BASIC or Pascal, in +which a variable often <EM>does</EM> get a new value, even after it's already +had a previous value assigned to it. Programs in those languages tend to be +full of things like "<CODE>X = X + 1</CODE>." Back in Chapter 2 we told +you that this book is about something called +"<A NAME="g4"></A><A NAME="g5"></A>functional programming," but we haven't yet explained exactly +what that means. (Of course we <EM>have</EM> introduced a lot of functions, +and that is an important part of it.) Part of what we mean by functional +programming is that once a variable exists, we aren't going to <EM>change</EM> the value of that variable. + +<P>The other possible source of confusion is that in Scheme, unlike the +situation in algebra, we may have more than one variable with the same name +at the same time. That's because we may invoke one procedure, and the body +of that procedure may invoke another procedure, and each of them might use the +same formal parameter name. There might be one variable named <CODE>x</CODE> with +the value 7, and another variable named <CODE>x</CODE> with the value 51, at the +same time. The pitfall to avoid is thinking "<CODE>x</CODE> has changed its value +from 7 to 51." + +<P>As an analogy, imagine that you are at a party along with Mick Jagger, Mick +Wilson, Mick Avory, and Mick Dolenz. If you're having a conversation with +one of them, the name "Mick" means a particular person to you. If you +notice someone else talking with a different Mick, you wouldn't think "Mick +has become a different person." Instead, you'd think "there are several +people here all with the name Mick." + +<P><H2>How Little People Do Variables</H2> + +<P><A NAME="g6"></A> You can understand variables in terms of the +little-people model. A variable, in this model, is the association in the +little person's mind between a formal parameter (name) and the actual +argument (value) she was given. When we want to know <CODE>(square 5)</CODE>, we +hire Srini and tell him his argument is 5. Srini therefore substitutes 5 +for <CODE>x</CODE> in the body of <CODE>square</CODE>. Later, when we want to know the +square of 6, we hire Samantha and tell her that her argument is 6. Srini and +Samantha have two different variables, both named <CODE>x</CODE>. + +<P><A NAME="srini"></A> +<CENTER><IMG SRC="../ss-pics/srini.jpg" ALT="figure: srini"></CENTER> + +<P>Srini and Samantha do their work separately, one after the other. But +in a more complicated example, there could even be more than +one value called <CODE>x</CODE> at the same time: + +<P><PRE>(define (square x) (* x x)) + +(define (<A NAME="g7"></A>hypotenuse x y) + (sqrt (+ (square x) (square y)))) + +> (hypotenuse 3 4) +5 +</PRE> + +<P>Consider the situation when we've hired Hortense to evaluate that +expression. Hortense associates the name <CODE>x</CODE> with the value 3 (and also +the name <CODE>y</CODE> with the value 4, but we're going to pay attention to <CODE>x</CODE>). She has to compute two <CODE>square</CODE>s. She hires Solomon to compute +<CODE>(square 3)</CODE>. Solomon associates the name <CODE>x</CODE> with the value 3. +This happens to be the same as Hortense's value, but it's still a separate +variable that could have had a different value—as we see when Hortense +hires Sheba to compute <CODE>(square 4)</CODE>. Now, simultaneously, Hortense +thinks <CODE>x</CODE> is 3 and Sheba thinks <CODE>x</CODE> is 4. + +<P><A NAME="sheba"></A> +<CENTER><IMG SRC="../ss-pics/hortense.jpg" ALT="figure: hortense"></CENTER> + +<P>(Remember that we said a variable is a connection between a name and a +value. So <CODE>x</CODE> isn't a variable! The association of the name <CODE>x</CODE> +with the value 5 is a variable. The reason we're being so fussy about this +terminology is that it helps clarify the case in which several variables +have the same name. But in practice people are generally sloppy about this +fine point; we can usually get away with saying "<CODE>x</CODE> is a variable" +when we mean "there is some variable whose name is <CODE>x</CODE>.") + +<P>Another important point about the way little people do variables is that +they can't read each others' minds. In particular, they don't know about +the values of the local variables that belong to the little people who +hired them. For example, the following attempt to compute the value 10 +won't work: + +<P><PRE>(define (f x) + (g 6)) + +(define (g y) + (+ x y)) + +> (f 4) +ERROR - VARIABLE X IS UNBOUND. +</PRE> + +<P>We hire Franz to compute <CODE>(f 4)</CODE>. He associates <CODE>x</CODE> with +4 and evaluates <CODE>(g 6)</CODE> by hiring Gloria. Gloria associates <CODE>y</CODE> +with 6, but she doesn't have any value for <CODE>x</CODE>, so she's in trouble. +The solution is for Franz to tell Gloria that <CODE>x</CODE> is <CODE>4</CODE>: + +<P><PRE>(define (f x) + (g x 6)) + +(define (g x y) + (+ x y)) + +> (f 4) +10 +</PRE> + +<P><H2>Global and Local Variables</H2> + +<P>Until now, we've been using two very different kinds of naming. We have +names for procedures, which are created permanently by <CODE>define</CODE> and are +usable throughout our programs; and we have names for procedure arguments, +which are associated with values temporarily when we call a +procedure and are usable only inside that procedure. + +<P>These two kinds of naming seem to be different in every way. One is for +procedures, one for data; the one for procedures makes a permanent, global +name, while the one for data makes a temporary, local name. That picture +does reflect the way that procedures and other data are <EM>usually</EM> used, +but we'll see that really there is only one kind of naming. The +boundaries can be crossed: Procedures can be arguments to other +procedures, and any kind of data +can have a permanent, global name. Right now we'll look at that last +point, about global variables. + +<P>Just as we've been using <CODE>define</CODE> to associate names with procedures +globally, we can also use it for other kinds of data: + +<P><PRE>> (define pi 3.141592654) + +> (+ pi 5) +8.141592654 + +> (define song '(I am the walrus)) + +> (last song) +WALRUS +</PRE> + +<P>Once defined, a global variable can be used anywhere, just as a defined +procedure can be used anywhere. (In fact, defining a procedure creates a +variable whose value is the procedure. Just as <CODE>pi</CODE> is the name of a +variable whose value is 3.141592654, <CODE>last</CODE> is the name of a variable +whose value is a primitive procedure. We'll come back to this +point in Chapter 9.) When the name of a global variable +appears in an expression, the corresponding value must be substituted, just +as actual argument values are substituted for formal parameters. + +<P>When a little person is hired to carry out a compound procedure, his or her +first step is to substitute actual argument values for formal parameters in +the body. The same little person substitutes values for global variable +names also. (What if there is a global variable whose name happens to be +used as a formal parameter in this procedure? Scheme's rule is that the +formal parameter takes precedence, but even though Scheme knows what to do, +conflicts like this make your program harder to read.) + +<P>How does this little person know what values to substitute for global +variable names? +<A NAME="g8"></A> +<A NAME="g9"></A> +What makes a variable "global" in the little-people model +is that <EM>every</EM> little person knows its value. You can imagine that +there's a big chalkboard, with all the global definitions written on it, that +all the little people can see. +If you prefer, you could imagine that whenever a global variable is defined, +the <CODE>define</CODE> specialist climbs up a huge ladder, picks up a megaphone, +and yells something like "Now hear this! <CODE>Pi</CODE> is 3.141592654!" + +<P>The association of a formal parameter (a name) with an actual argument (a +value) is called a <EM><A NAME="g10"></A><A NAME="g11"></A>local variable.</EM> + +<P>It's awkward to have to say "Harry associates the value 7 with the name +<CODE>foo</CODE>" all the time. Most of the time we just say "<CODE>foo</CODE> has the +value 7," paying no attention to whether this association is in some +particular little person's head or if everybody knows it. + +<P><H2>The Truth about Substitution</H2> + +<P>We said earlier in a footnote that Scheme doesn't actually do all the +copying and substituting we've been talking about. What actually happens is +<A NAME="g12"></A> +more like our model of global variables, in which there is a chalkboard +somewhere that associates names with values—except that instead of making +a new copy of every expression with values substituted for names, Scheme +works with the original expression and looks up the value for each +name at the moment when that value is needed. To make local variables work, +there are several chalkboards: a global one and one for each little person. + +<P>The fully detailed model of variables using several chalkboards is what many +people find hardest about learning Scheme. That's why we've chosen to use +the simpler substitution model.<A NAME="text2" HREF="variables.html#ft2">[2]</A> + +<P><H2><CODE>Let</CODE></H2> + +<P>We're going to write a procedure that solves quadratic equations. (We know +this is the prototypical boring programming problem, but it illustrates +clearly the point we're about to make.) + +<P>We'll use the quadratic formula that you learned in high school +algebra class: + +<P><P><CENTER><IMG SRC="math1.gif" ALT="math display"></CENTER><P> + +<P><PRE>(define (roots a b c) + (se (/ (+ (- b) (sqrt (- (* b b) (* 4 a c)))) + (* 2 a)) + (/ (- (- b) (sqrt (- (* b b) (* 4 a c)))) + (* 2 a)))) +</PRE> + +<P>Since there are two possible solutions, we return a sentence containing two +numbers. This procedure works fine,<A NAME="text3" HREF="variables.html#ft3">[3]</A> but it does have the disadvantage of repeating a +lot of the work. It computes the square root part of the formula twice. +We'd like to avoid that inefficiency. + +<P>One thing we can do is to compute the square root and use that as the +actual argument to a helper procedure that does the rest of the job: + +<P><PRE>(define (roots a b c) + (roots1 a b c (sqrt (- (* b b) (* 4 a c))))) + +(define (roots1 a b c discriminant) + (se (/ (+ (- b) discriminant) (* 2 a)) + (/ (- (- b) discriminant) (* 2 a)))) +</PRE> + +<P>This version evaluates the square root only once. The resulting +value is used as the argument named <CODE>discriminant</CODE> in <CODE>roots1</CODE>. + +<P>We've solved the problem we posed for ourselves initially: avoiding the +redundant computation of the discriminant (the square-root part of the +formula). The cost, though, is that we had to define an auxiliary procedure +<CODE>roots1</CODE> that doesn't make much sense on its own. (That is, you'd never +invoke <CODE>roots1</CODE> for its own sake; only <CODE>roots</CODE> uses it.) + +<P>Scheme provides a notation to express a computation of this kind more +<A NAME="splet"></A> +conveniently. It's called <A NAME="g13"></A><CODE>let</CODE>: + +<P><PRE>(define (roots a b c) + (let ((discriminant (sqrt (- (* b b) (* 4 a c))))) + (se (/ (+ (- b) discriminant) (* 2 a)) + (/ (- (- b) discriminant) (* 2 a))))) +</PRE> + +<P>Our new program is just an abbreviation for the previous version: +In effect, it creates a temporary procedure just like <CODE>roots1</CODE>, but +without a name, and invokes it with the specified argument value. But the +<CODE>let</CODE> notation rearranges things so that we can say, in the right order, +"let the variable <CODE>discriminant</CODE> have the value <CODE>(sqrt&hellip)</CODE> +and, using that variable, compute the body." + +<P><CODE>Let</CODE> is a <A NAME="g14"></A><A NAME="g15"></A>special form that takes two arguments. The first is +a sequence of name-value pairs enclosed in parentheses. (In this example, +there is only one name-value pair.) The second argument, the <EM>body</EM> +of the <CODE>let</CODE>, is the expression to evaluate. + +<P> +Now that we have this notation, we can use it with more than one name-value +connection to eliminate even more redundant computation: + +<P><PRE>(define (<A NAME="g16"></A>roots a b c) + (let ((discriminant (sqrt (- (* b b) (* 4 a c)))) + (minus-b (- b)) + (two-a (* 2 a))) + (se (/ (+ minus-b discriminant) two-a) + (/ (- minus-b discriminant) two-a)))) +</PRE> + +<P>In this example, the first argument to <CODE>let</CODE> includes three +name-value pairs. It's as if we'd defined and invoked a procedure like +the following: + +<P><PRE>(define (roots1 discriminant minus-b two-a) ...) +</PRE> + +<P>Like <CODE>cond</CODE>, <CODE>let</CODE> uses parentheses both with the usual meaning +(invoking a procedure) and to group sub-arguments that belong together. This +<A NAME="g17"></A> +grouping happens in two ways. Parentheses are used to group a name and the +expression that provides its value. Also, an additional pair of parentheses +surrounds the entire collection of name-value pairs. + +<P> +<P><H2>Pitfalls</H2> + +<P>If you've programmed before in other languages, you may be accustomed +to a style of programming in which you <EM>change</EM> the value of a +variable by assigning it a new value. You may be tempted to write + +<P><PRE>> (define x (+ x 3)) ;; no-no +</PRE> + +<P>Although some versions of Scheme do allow such redefinitions, so +that you can correct errors in your procedures, they're not strictly legal. +A definition is meant to be <EM>permanent</EM> in functional programming. +(Scheme does include other mechanisms for non-functional programming, but +we're not studying them in this book because once you allow reassignment you +need a more complex model of the evaluation process.) + +<P>When you create more than one temporary variable at once using <CODE>let</CODE>, all of the expressions that provide the values are computed before any +of the variables are created. Therefore, you can't have one expression +depend on another: + +<P><PRE>> (let ((a (+ 4 7)) ;; wrong! + (b (* a 5))) + (+ a b)) +</PRE> + +<P>Don't think that <CODE>a</CODE> gets the value 11 and therefore <CODE>b</CODE> +gets the value 55. That <CODE>let</CODE> expression is equivalent to defining a +helper procedure + +<P><PRE>(define (helper a b) + (+ a b)) +</PRE> + +<P>and then invoking it: + +<P><PRE>(helper (+ 4 7) (* a 5)) +</PRE> + +<P>The argument expressions, as always, are evaluated <EM>before</EM> +the function is invoked. The expression <CODE>(* a 5)</CODE> will be evaluated +using the <EM>global</EM> value of <CODE>a</CODE>, if there is one. If not, an +error will result. If you want to use <CODE>a</CODE> in computing <CODE>b</CODE>, you +must say + +<P><PRE>> (let ((a (+ 4 7))) + (let ((b (* a 5))) + (+ a b))) +66 +</PRE> + +<P><CODE>Let</CODE>'s notation is tricky because, like <CODE>cond</CODE>, it uses +parentheses that don't mean procedure invocation. Don't teach yourself magic +formulas like "two open parentheses before the <CODE>let</CODE> variable and three +close parentheses at the end of its value." Instead, think about the +overall structure: + +<P><PRE>(let variables body) +</PRE> + +<P><CODE>Let</CODE> takes exactly two arguments. The first argument to <CODE>let</CODE> is one or more name-value groupings, all in parentheses: + +<P><PRE>((name1 value1) (name2 value2) (name3 value3) &hellip) +</PRE> + +<P>Each <CODE>name</CODE> is a single word; each <CODE>value</CODE> can be any +expression, usually a procedure invocation. If it's a procedure invocation, +then parentheses are used with their usual meaning. + +<P>The second argument to <CODE>let</CODE> is the expression to be evaluated using +those variables. + +<P>Now put all the pieces together: + +<P><PRE>(let <STRONG><BIG>((</BIG></STRONG>name1 (fn1 arg1)<STRONG><BIG>)</BIG></STRONG> + <STRONG><BIG> (</BIG></STRONG>name2 (fn2 arg2)<STRONG><BIG>)</BIG></STRONG> + <STRONG><BIG> (</BIG></STRONG>name3 (fn3 arg3)<STRONG><BIG>))</BIG></STRONG> + body) +</PRE> + +<P> +<H2>Boring Exercises</H2> + +<P><B>7.1</B> The following procedure does some redundant computation. + +<P><PRE>(define (<A NAME="g18"></A>gertrude wd) + (se (if (vowel? (first wd)) 'an 'a) + wd + 'is + (if (vowel? (first wd)) 'an 'a) + wd + 'is + (if (vowel? (first wd)) 'an 'a) + wd)) + +> (gertrude 'rose) +(A ROSE IS A ROSE IS A ROSE) + +> (gertrude 'iguana) +(AN IGUANA IS AN IGUANA IS AN IGUANA) +</PRE> + +<P>Use <CODE>let</CODE> to avoid the redundant work. + + +<P> +<B>7.2</B> Put in the missing parentheses: + +<P><PRE>> (let pi 3.14159 + pie 'lemon meringue + se 'pi is pi 'but pie is pie) +(PI IS 3.14159 BUT PIE IS LEMON MERINGUE) +</PRE> + +<P> +<H2>Real Exercises</H2> + +<P><B>7.3</B> The following program doesn't work. Why not? Fix it. + +<P><PRE>(define (<A NAME="g19"></A>superlative adjective word) + (se (word adjective 'est) word)) +</PRE> + +<P>It's supposed to work like this: + +<P><PRE>> (superlative 'dumb 'exercise) +(DUMBEST EXERCISE) +</PRE> + +<P> +<B>7.4</B> What does this procedure do? Explain how it manages to work. + +<P><PRE>(define (<A NAME="g20"></A>sum-square a b) + (let ((+ *) + (* +)) + (* (+ a a) (+ b b)))) +</PRE> + +<P> + +<HR> +<A NAME="ft1" HREF="variables.html#text1">[1]</A> The term "variable" is used by +computer scientists to mean several subtly different things. For example, +some people use "variable" to mean just a holder for a value, without a +name. But what we said is what <EM>we</EM> mean by "variable."<P> +<A NAME="ft2" HREF="variables.html#text2">[2]</A> The reason that all of our +examples work with the substitution model is that this book uses only +functional programming, in the sense that we never change the value of a +variable. If we started doing the <CODE>X = X + 1</CODE> style of programming, we +would need the more complicated chalkboard model.<P> +<A NAME="ft3" HREF="variables.html#text3">[3]</A> That is, it works if the equation +has real roots, or if your version of Scheme has complex numbers. Also, the +limited precision with which computers can represent irrational numbers can +make this particular algorithm give wrong answers in practice even though +it's correct in theory.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch6/true.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch8/part3.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |