Though not often used in business, Scheme and its cousin Common Lisp which the book describes in an appendix are still favored by computer scientists, for example, in artificial intelligence research. Simple Scheme succeeds in making a difficult programming language both approachable and accessible.
It's a valuable resource to any computer science student who is taking Scheme on for the first time. Topics covered : Scheme language fundamentals, functions and higher-order functions, variables, lambda basics, recursion, abstraction, software patterns in Scheme, lists, trees, sequential programming, working with files, vectors, Common Lisp.
Convert currency. Add to Basket. Book Description Condition: Brand New. Printing in English language. We may ship the books from Asian regions for inventory purpose Edition: U. More information about this seller Contact this seller. We may ship the books from Asian regions for inventory purpose. Condition: New. Seller Inventory mon New Book. Shipped from UK. Established seller since Seller Inventory WM Never used!. Seller Inventory P Seller Inventory M Book Description Condition: New.
Seller Inventory n. Language: English. Brand new Book. Seller Inventory AAH Brian Harvey ; Matthew Wright. This specific ISBN edition is currently not available. View all copies of this ISBN edition:. The second chapter explores functions in some detail. Traditionally, computer programs are built out of actions: First do this, then do that, and finally print the results. Each step in the program does something. Functional programming is different, in that we are less concerned with actions and more concerned with values. For example, if you have a pocket calculator with a square root button, you could enter the number 3, push the button, and you'll see something like 1.
How does the calculator know? There are several possible processes that the calculator could carry out. One process, for example, is to make a guess, square it, see if the result is too big or too small, and use that information to make a closer guess. That's a sequence of actions. But ordinarily you don't care what actions the calculator takes; Page 3.
We're going to focus on this business of functions, arguments, and result values. Don't think that functions have to involve numbers. We'll be working with functions like ''first name," "plural," and "acronym. Page 4. The ideas are mostly about control of complexitythat is, about how to develop a large computer program without being swamped in details. For example, once you've solved part of the large problem, you can give that partial solution a name and then you can use the named subprogram as if it were an indivisible operation, just like the ones that are built into the computer.
Thereafter, you can forget about the details of that subprogram. This is the beginning of the idea of abstraction, which we'll discuss in more depth throughout the book. The big ideas are what this book is about, but first we're going to introduce you to Scheme. Scheme is a dialect of Lisp, a family of computer programming languages invented for computing with words, sentences, and ideas instead of just numbers. Talking to Scheme The incantations to get Scheme running will be different for each model of computer. Appendix A talks about these details; you can look up the particular version of Scheme that you're using.
That appendix will also tell you how to load the file simply. When Scheme has started up and is ready for you to interact with it, you'll see a message on the screen, something like this: Welcome to XYZ Brand Scheme. Scheme is an interactive programming language. In other words, you type a request to Scheme, then Scheme prints the answer, and then you get another prompt.
We just asked Scheme, "What is 6? Whenever something you type to Scheme is enclosed in parentheses, it indicates a request to carry out a procedure. We'll define "procedure" more formally later, but for now it means something that Scheme knows how to do. A procedure tells Scheme how to compute a particular function. The first thing inside the parentheses indicates what procedure to use; the others are arguments, i. If this last example gives an error message saying that Scheme doesn't understand the name word, it means that you didn't load the file simply.
Consult Appendix A. In these first examples, we've shown that you type in boldface and what the computer responds in lightface. Hereafter, we will rely on the prompt characters to help you figure out who's talking on which line. For the examples in this book, we'll assume that you always type in lower case and that the computer prints in upper case. Your Scheme might print in lower case; it doesn't matter.
Recovering from Typing Errors Don't worry if you make a mistake typing these examples in; you can just try again. One of the great things about interactive programming languages is that you can experiment in them. The parentheses and single quote marks are important; don't leave them out. If Scheme seems to be ignoring you, try typing a bunch of right parentheses, , and hitting the return or enter key. That's because Scheme doesn't do anything until you've closed all the parentheses you've opened, so if you have an extra left parenthesis, you can keep typing forever with no response.
Another problem you might encounter is seeing a long message that you don't understand and then finding yourself with something other than a Scheme prompt. This happens when Scheme considers what you typed as an error. Here's an example; for now, never mind exactly why this is an error. The exact form of the message you get will depend on the version of Scheme that you're using. For now, the important point is that some versions deal with errors by leaving you talking to a debugger instead of to Scheme itself.
The debugger may have a completely different language. It's meant to help you figure out what's wrong in a large program you've written. For a beginner, though, it's more likely to get in the way. Read the documentation for your particular Scheme dialect to learn how to escape from the debugger.
In some versions you don't get trapped in a debugger when you make an error, so this problem may not arise. If you type in some of the examples that follow and then exit from Scheme, what you type won't be remembered the next time you use Scheme. Appendix A talks about how to use a text editor along with Scheme to make a permanent record of your work. More Examples We're about to show you a few examples of we hope interesting programs in Scheme.
Play with them! Type them into your computer and try invoking them with different data. Again, don't worry too much if something doesn't workit probably just means that you left out a parenthesis, or some such thing. While you're going through these examples, see how much you can figure out for yourself about how they work. In particular, try guessing what the names of procedures, such as first and keep, mean. Some of them will probably be obvious, some of them harder. The point isn't to see how smart you are, but to get you thinking about the kinds of things you want to be able to do in a computer program.
Later on we'll go through these examples in excruciating detail and tell you the official meanings of all the pieces. Besides learning the vocabulary of Scheme, another point of this activity is to give you a feeling for the ways in which we put these names together in a program. Every programming language has its own flavor. For example, if you've programmed before in other languages, you may be surprised not to find anything that says print in these examples.
On the other hand, some of these examples are programs that we won't expect you to understand fully until most of the way through this book. So don't worry if something doesn't make sense; just try to get some of the flavor of Scheme programming. Example: Acronyms Here's our first new program. When you first start up Scheme, it knows procedures. These are called primitive procedures. Programming in Scheme means defining new procedures, called compound procedures. Did you have trouble figuring out what all the pieces do in the acronym procedure?
We can rewrite the program to leave out certain words: define acronym phrase accumulate word every first keep realword? Pig Latin is a not-very-secret secret language that many little kids learn. Each word is translated by moving all the initial consonants to the end of the word, and adding "ay" at the end. It's usually spoken rather than written, but that's a little harder to do on a computer. That's not how it works in Scheme.
The entire thing is a single expression, and what counts is the grouping with parentheses. Starting a new line is no different from a space between words as far as Scheme is concerned. We could have defined pigl on one humongous line and it would mean the same thing. Also, Scheme doesn't care about how we've indented the lines so that subexpressions line up under each other. We do that only to make the program more readable for human beings.
The procedure follows one of two possible paths, depending on whether the first letter of the given word is a vowel. You've seen every before, in the acronym example, but we haven't told you what it does. Try to guess what Scheme will respond when you type this: every pigl ' the ballad of john and yoko Page Example: Ice Cream Choices Here's a somewhat more complicated program, but still pretty short considering what it accomplishes:. Notice that in writing the program we didn't have to say how many menu categories there are, or how many choices in each category.
This one program will work with any menutry it out yourself. Page Example: Combinations from a Set Here's a more mathematical example. We want to know all the possible combinations of, let's say, three things from a list of five possibilities. For example, we want to know all the teams of three people that can be chosen from a group of five people. Although this will be a pretty short program, it's more complicated than it looks. We don't expect you to be able to figure out the algorithm yet. If you're trying to figure out the algorithm despite our warning, here's a hint: All the combinations of three letters shown above can be divided into two groups.
The first group consists of the ones that start with the letter A and contain two more letters; the second group has three letters not including A. The procedure finds these two groups separately and combines them into one. If you want to try to understand all the pieces, try playing with them separately, as we encouraged you to do with the pigl and acronym procedures.
What's an algorithm? It's a method for solving a problem. The usual analogy is to a recipe in cooking, although you'll see throughout this book that we want to get away from the aspect of that analogy that emphasizes the sequential nature of a recipefirst do this, then do that, etc. There can be more than one algorithm to solve the same problem. If you've taken a probability course, you know that there is a formula for the number of possible combinations. The most traditional use of computers is to work through such formulas and compute numbers. However, not all problems are numeric.
Lisp, the programming language family of which Scheme is a member, is unusual in its emphasis on symbolic computing. In this example, listing the actual combinations instead of just counting them is part of the flavor of symbolic computing, along with our earlier examples about manipulating words and phrases. We'll try to avoid numeric problems when possible, because symbolic computing is more fun for most people.
Example: Factorial Scheme can handle numbers, too. The factorial of n usually written in mathematical notation as n! If this doesn't work because your computer is too small, try a more reasonably sized example, such as the factorial of Play with the Procedures This chapter has introduced a lot of new ideas at once, leaving out all the details. Our hope has been to convey the flavor of Scheme programming, before we get into Chapter 2, which is full of those missing details.
But you can't absorb the flavor just by reading; take some time out to play with these examples before you go on. Exercises 1. Load the file into Scheme and run the program. Produce a transcript file called acronym. We can't give a complete definition of this term yet, but in this chapter we introduce the building block of functional programming, the function.
Basically we mean by "function" the same thing that your high school algebra teacher meant, except that our functions don't necessarily relate to numbers. In that example, f is the name of a function; that function takes an argument called x, which is a number, and returns some other number.
In this chapter you are going to use the computer to explore functions, but you are not going to use the standard Scheme notation as in the rest of the book. That's because, in this chapter, we want to separate the idea of functions from the complexities of programming language notation. For example, real Scheme notation lets you write expressions that involve more than one function, but in this chapter you can only use one at a time. To get into this chapter's special computer interface, first start running Scheme as you did in the first chapter, then type load "functions.
If you have trouble loading the program, look in Appendix A for further information about load.
Then, to start the program, type. You'll then be able to carry out interactions like the following. As you can see, different functions can have different numbers of arguments. In these examples we added two numbers, and we took the square root of one number. However, every function gives exactly one result each time we use it.
To leave the functions program, type exit when it asks for a function. Try different kinds of numbers, including integers and numbers with decimal fractions. What if you try to divide by zero? Throughout this chapter we are going to let you experiment with functions rather than just give you a long, boring list of how each one works. The boring list is available for reference on page If you get no response at all after you type functions , just press the Return or Enter key again.
Tell your instructor to read Appendix A to see how to fix this. These are just a few suggestions. Be creative; don't just type in our examples. Words Not all Scheme functions deal with numbers. A broader category of argument is the word, including numbers but also including English words like spaghetti or xylophone. Even a meaningless sequence of letters and digits such as glrp is considered a word. What happens if you use a number as the argument to one of these? Function: butfirst Argument: a Function: count Argument: So far most of our functions fall into one of two categories: the arithmetic functions, which require numbers as arguments and return a number as the result; and the word functions, which accept words as arguments and return a word as the result.
The one exception we've seen is count. What kind of argument does count accept? What kind of value does it return? The technical term for "a kind of data" is a type. In principle you could think of almost anything as a type, such as "numbers that contain the digit 7. Types can overlap; for example, numbers are also considered words. Function: word Argument: 3. Certain punctuation characters can also be used in words, but let's defer the details until you've gotten to know the word functions with simpler examples.
Domain and Range The technical term for "the things that a function accepts as an argument" is the domain of the function. The name for "the things that a function returns" is its range. So the domain of count is words, and the range of count is numbers in fact, nonnegative integers. This example shows that the range may not be exactly one of our standard data types; there is no "nonnegative integer" type in Scheme. How do you talk about the domain and range of a function? You could say, for example, "The cos function has numbers as its domain and numbers between 1 and 1 as its range.
For functions of two or more arguments, the language is a little less straightforward. The informal version still works: "Remainder takes two integers as arguments and returns an integer. But we don't want to go into all the bells and whistles at once, so we'll start with adding two numbers at a time.
Here are examples that illustrate the domains of some functions: Function: expt Argument: 3 Argument:. Real mathematicians say, "The domain of remainder is the Cartesian cross product of the integers and the integers. More Types: Sentences and Booleans We're going to introduce more data types, and more functions that include those types in their domain or range. The next type is the sentence: a bunch of words enclosed in parentheses, such as all you need is love.
Don't include any punctuation characters within the sentence. Many of the functions that accept words in their domain will also accept sentences. There is also a function sentence that accepts words and sentences. Try examples like butfirst of a sentence. Function: sentence Argument: when i get Argument: home Function: butfirst Argument: yer blues Function: butlast Argument:.
Other important functions are used to ask yes-or-no questions. That is, the range of these functions contains only two values, one meaning "true" and the other meaning "false. The question mark is part of the name of the function. There are also functions and, or, and not whose domain and range are both true-false values. The two values "true" and "false" are called Booleans, named after George Boole , who developed the formal tools used for true-false values in mathematics. What good are these true-false values? Often a program must choose between two options: If the number is positive, do this; if negative, do that.
Scheme has functions to make such choices based on true-false values. For now, you can experiment with the if function. Its first argument must be true or false; the others can be anything. Scheme has several more data types, but for now we'll just consider one more. A function can be used as data. Here's an example: Page 22 Function: numberofarguments Argument: equal? The result is: 2. The range of numberofarguments is nonnegative integers.
But its domain is functions. For example, try using it as an argument to itself! If you've used other computer programming languages, it may seem strange to use a functionthat is, a part of a computer programas data. Most languages make a sharp distinction between program and data.
We'll soon see that the ability to treat functions as data helps make Scheme programming very powerful and convenient. Try these examples: Function: every Argument: first Argument: the long and winding road Function: keep Argument: vowel? Argument: constantinople. Think carefully about these. You aren't applying the function first to the sentence the long and winding road ; you're applying the function every to a function and a sentence. Other functions that can be used with keep include even? Play with It If you've been reading the book but not trying things out on the computer as you go along, get to work!
Spend some time getting used to these ideas and thinking about them. When you're done, read ahead. Thinking about What You've Done The idea of function is at the heart of both mathematics and computer science. For example, when mathematicians want to think very formally about the system of numbers, they use functions to create the integers. They say, let's suppose we have one number,. Functions are important in computer science because they give us a way to think about processin simple English, a way to think about something happening, something changing.
A function embodies a transformation of information, taking in something we know and returning something we didn't know. That's what computers do: They transform information to produce new results. A lot of the mathematics taught in school is about numbers, but we've seen that functions don't have to be about numbers. We've used functions of words and sentences, such as first, and even functions of functions, such as keep. You've done a lot of thinking about the domain and range of functions. You can add two numbers, but it doesn't make sense to add two words that aren't numbers.
Some two-argument functions have complicated domains because the acceptable values for one argument depend on the specific value used for the other one. The function expt is an example; make sure you've tried both positive and negative numbers, and fractional as well as whole-number powers. Part of the definition of a function is that you always get the same answer whenever you call a function with the same argument s. The value returned by the function, in other words, shouldn't change regardless of anything else you may have computed meanwhile.
One of the ''functions" you've explored in this chapter isn't a real function according to this rule; which one? The rule may seem too restrictive, and indeed it's often convenient to use the name "function" loosely for processes that can give different results in different circumstances. But we'll see that sometimes it's important to stick with the strict definition and refrain from using processes that aren't truly functions. We've hinted at two different ways of thinking about functions.
The first is called function as process. Here, a function is a rule that tells us how to transform some information into some other information. The function is just a rule, not a thing in its own right. The actual "things" are the words or numbers or whatever the function manipulates. The second way of thinking is called function as object. In this view, a function is a perfectly good "thing" in itself.
We can use a function as an argument to another function, for example. Research with college math students shows that this second idea is hard for most people, but it's worth the effort because you'll see that higher-order functions functions of functions like keep and every can make programs much easier to write.
As a homey analogy, think about a carrot peeler. If we focus our attention on the carrotswhich are, after all, what we want to eatthen the peeler just represents a process. We are peeling carrots. We are applying the function peel to carrots. It's the carrot that counts. But we can also think about the peeler as a thing in its own right, when we clean it, or worry about whether its blade is sharp enough.
The big idea that we haven't explored in this chapter although we used it a lot in Chapter 1 is the composition of functions: using the result from one function as an argument to another function.
It's a crucial idea; we write large programs by defining a bunch of small functions and then composing them with each other to produce the desired result. We'll start doing that in the next chapter, where we return to real Scheme notation. Exercises Use the functions program for all these exercises. Fill in the missing details.
Experiment with it, and then describe fully its domain and range, and what it does. Make sure to try lots of cases. Hint: Think about its name. The following exercises ask for functions that meet certain criteria. Which of the functions you've seen in this chapter satisfy that definition? Which of the operators from Exercise 2. It's that we can take the value returned by one function and use it as an argument to another function. By "hooking up" two functions in this way, we invent a new, third function.
When we give an example like this at the beginning of a part, don't worry about the fact that you don't recognize the notation. The example is meant as a preview of what you'll learn in the coming chapters. We know that this idea probably doesn't look like much of a big deal to you. It seems obvious. Nevertheless, it will turn out that we can express a wide variety of computational algorithms by linking functions together in this way.
This linking is what we mean by "functional programming. We're emphasizing the word "evaluates" because the essence of understanding Scheme is knowing what it means to evaluate something. Each question you type is called an expression. The metaphor is from chemistry, where atoms of single elements are combined to form chemical compounds. We sometimes call the expressions within a compound expression its subexpressions.
Compound expressions tell Scheme to "do" a procedure.
This idea is so important that it has a lot of names. You can call a procedure; you can invoke a procedure; or you can apply a procedure to some numbers or other values. All of these mean the same thing. If you've programmed before in some other language, you're probably accustomed to the idea of several different types of statements for different purposes. For example, a "print statement" may look very different from an "assignment statement. In other programming languages, the name for what you type might be a "command" or an "instruction.
Also, in Scheme we are more often asking questions rather than telling the computer to take some action. Whatever you want to do, there's only one notation: the compound expression. Notice that we said a compound expression contains expressions. This means that you can't understand what an expression is until you already understand what an expression is. How do you ever get a handle on this self-referential idea? The secret is that there has to be some simple kind of expression that doesn't have smaller expressions inside itthe atomic expressions. It's easy to understand an expression that just contains one number.
Numbers are self-evaluating; that is, when you evaluate a number, you just get the same number back. Once you understand numbers, you can understand expressions that add up numbers. And once you understand those expressions, you can use that knowledge to figure out expressions that add up expressions-that-add-up-numbers.
In practice, you don't usually think about all these levels of complexity separately. You just think, "I know what a number is, and I know what it means to add up any expressions. But in Scheme, parentheses are never optional. Every procedure call must be enclosed in parentheses. Little People You may not have realized it, but inside your computer there are thousands of little people.
Each of them is a specialist in one particular Scheme procedure. The head little person, Alonzo, is in charge of the read-eval-print loop. Alonzo reads it, hires other little people to help him evaluate it, and finally prints 7, its value. We're going to focus on the evaluation step. Three little people work together to evaluate the expression: a minus person and two plus people. Don't be confused by this and try to type minus to Scheme.
Since the overall expression is a subtraction, Alonzo hires Alice, the first available minus specialist. Here's how the little people evaluate the expression: Alice wants to be given some numbers, so before she can do any work, she complains to Alonzo that she wants to know which numbers to subtract. Since both of these are addition problems, Alonzo hires two plus specialists, Bernie and Cordelia, and tells them to report their results to Alice. The first plus person, Bernie, also wants some numbers, so he asks Alonzo for them. Since these are both atomic, Alonzo can give them directly to Bernie.
Bernie adds his arguments, 5 and 8, to get He does this in his headwe don't have to worry about how he knows how to add; that's his job. She adds them, getting 6. Bernie and Cordelia hand their results to the waiting Alice, who can now subtract them to get 7. She hands that result to Alonzo, who prints it. How does Alonzo know what's the argument to what? That's what the grouping of subexpressions with parentheses is about.
Since the plus expressions are inside the minus expression, the plus people have to give their results to the minus person. We've made it seem as if Bernie does his work before Cordelia does hers. In fact, the order of evaluation of the argument subexpressions is not specified in Scheme; different implementations may do it in different orders. In particular, Cordelia might do her work before Bernie, or they might even do their work at the same time, if we're using a parallel processing computer. However, it is important that both Bernie and Cordelia finish their work before Alice can do hers.
This says to multiply the numbers 7 and 5, except that instead of saying 7 and 5 explicitly, we wrote expressions whose values are 7 and 5. The argument subexpressions, in turn, have their own subexpressions. We can express this organization of little people more formally. If an expression is atomic, Scheme just knows the value. Those other subexpressions are the arguments.
We can use this rule to evaluate arbitrarily complex expressions, and Scheme won't get confused. No matter how long the expression is, it's made up of smaller subexpressions to which the same rule applies. Scheme ignores everything to the right of a semicolon, so semicolons can be used to indicate comments, as above. In the functions program of Chapter 2 we pretended that every Scheme function accepts a fixed number of arguments, but actually, some functions can accept any number.
Result Replacement Since a little person can't do his or her job until all of the necessary subexpressions have been evaluated by other little people, we can "fast forward" this process by skipping the parts about "Alice waits for Bernie and Cordelia" and starting with the completion of the smaller tasks by the lesser little people. To keep track of which result goes into which larger computation, you can write down a complicated expression and then rewrite it repeatedly, each time replacing some small expression with a simpler expression that has the same value.
In each line of the diagram, the boxed expression is the one that will be replaced with its value on the following line. If you like, you can save some steps by evaluating several small expressions from one line to the next:. Plumbing Diagrams Some people find it helpful to look at a pictorial form of the connections among subexpressions.
You can think of each procedure as a machine, like the ones they drew on the chalkboard in junior high school. Each machine has some number of input hoppers on the top and one chute at the bottom. You put something in each hopper, turn the crank, and something else comes out the bottom. For a complicated expression, you hook up the output chute of one machine to the input hopper of another. These combinations are called "plumbing diagrams. You can annotate the diagram by indicating the actual information that flows through each pipe.
Below this short table of contents is an expanded table of contents including sections within each chapter. Click on the chapter name to jump down. You can also. In these first two chapters, our goal is to introduce the Scheme programming language and the idea of using functions as the building blocks of a computation.
Here's how that would look for this expression:. Pitfalls One of the biggest problems that beginning Lisp programmers have comes from trying to read a program from left to right, rather than thinking about it in terms of expressions and subexpressions. For example, square cos 3. Another big problem that people have is thinking that Scheme cares about the spaces, tabs, line breaks, and other "white space" in their Scheme programs.
We've been indenting our expressions to illustrate the way that subexpressions line up underneath each other. A consequence of Scheme's not caring about white space is that when you hit the return key, Scheme might not do anything. If you're in the middle of an expression, Scheme waits until you're done typing the entire thing before it evaluates what you've typed.
So if Scheme seems to be ignoring you, try typing a zillion close parentheses. You'll probably get an error message about too many parentheses, but after that, Scheme should start paying attention again. You might get into the same sort of trouble if you have a double-quote mark " in your program. Everything inside a pair of quotation marks is treated as one single string.
We'll explain more about strings later. Once you type the second quotation mark, you may still need some close parentheses, since the ones you type inside a string don't count. One other way that Scheme might seem to be ignoring you comes from the fact that you don't get a new Scheme prompt until you type in an expression and it's evaluated.
So if you just hit the return or enter key without typing anything, most versions of Scheme won't print a new prompt. Boring Exercises 3. How many subexpressions not including subexpressions of subexpressions does each one have? Give each little person a name and list her specialty, the argument values she receives, her return value, and the name of the little person to whom she tells her result. Some Schemes return a decimal fraction like 0. Real Exercises 3. It is a compound expression made up of three atoms. For this problem, write five other Scheme expressions whose values are also the number ten: An atom Another compound expression made up of three atoms A compound expression made up of four atoms A compound expression made up of an atom and two compound subexpressions Any other kind of expression Page In this chapter you'll find out how to create new procedures.
How to Define a Procedure A Scheme program consists of one or more procedures. A procedure is a description of the process by which a computer can work out some result that we want. The value returned by define may differ depending on the version of Scheme you're using. Many versions return the name of the procedure you're defining, but others return something else. It doesn't matter, because when you use define you aren't interested in the returned value, but rather in the fact that Scheme remembers the new definition for later use. This is the definition of a procedure called square.
Square takes one argument, a number, and it returns the square of that number. This procedure definition has four parts. The first is the word define, which indicates that you are defining something. The second and third come together inside parentheses: the name that you want to give the procedure and the name s you want to use for its argument s. This arrangement was chosen by the designers of Scheme because it looks like the form in which the procedure will be invoked.
That is, square x looks like square 7. The fourth part of the definition is the body: an expression whose value provides the function's return value. Special Forms Define is a special form, an exception to the evaluation rule we've been going on about. The specialness of special forms is that Scheme doesn't evaluate all the subexpressions. Instead, each special form has its own particular evaluation rule. It wouldn't make sense to evaluate square x because you can't invoke the square procedure before you define it!
Technically, the entire expression define square x But in fact Lispians are almost always loose about this distinction and say "define is a special form," just as we've done here. The word "form" is an archaic synonym for "expression," so "special form" just means "special expression. It would be possible to describe special forms using the following model: "Certain procedures want their arguments unevaluated, and Scheme recognizes them.
After refraining from evaluating define's arguments, for example, Scheme invokes the define procedure with those unevaluated arguments. The entire special form that starts with define is just a completely different kind of thing from a procedure call. In Scheme there is no procedure named define. Nevertheless, in this book, unless it's really important to make the distinction, we'll talk as if there were a procedure called define.
For example, we'll talk about "define's arguments" and "the value returned by define" and "invoking define. Throughout most of this book, our procedures will describe processes that compute functions. A function is a connection between some values you already know and a new value you want to find out. For example, the square function takes a number, such as 8, as its input value and returns another number, 64 in this case, as its output value.
The plural function takes a noun, such as "computer," and returns another word, "computers" in this example. The technical term for the function's input value is its argument. A function may take more than one argument; for example, the remainder function takes two arguments, such as 12 and 5. It returns one value, the remainder on dividing the first argument by the second in this case, 2. We said earlier that a procedure is "a description of the process by which a computer can work out some result that we want. For example, to compute f 8 we'd multiply 8 by 3, then add 12 to the result.
To compute g 8 , we'd add 4 to Page But we get the same answer, 36, either way. These two equations describe different processes, but they compute the same function. The function is just the association between the starting value s and the resulting value, no matter how that result is computed. In real life, functions are not always represented by procedures. We could represent a function by a table showing all its possible values, like this: Alabama Alaska Arizona Arkansas California This table represents the State Capital function; we haven't shown all the lines of the complete table, but we could.
There are only a finite number of U. Numeric functions can also be represented by graphs, as you probably learned in high school algebra. In this book our focus is on the representation of functions by procedures.
Defining Your Own Procedures. Lisp, the programming language family of which Scheme is a member, is unusual in its emphasis on symbolic computing. More information about this seller Contact this seller 8. To ask other readers questions about Simply Scheme , please sign up. This goal is supported by the use of Scheme, a modern dialect of Lisp, designed to emphasize symbolic programming.
The only reason for showing you this table example is to clarify what we mean when we say that a function is represented by a procedure, rather than that a function is the procedure. We'll say "the procedure f" when we want to discuss the operations we're telling Scheme to carry out. We'll say "the function represented by f" when our attention is focused on the value returned, rather than on the mechanism. But we'll often abbreviate that lengthy second phrase with "the function f" unless the context is especially confusing.
Also, we'll sometimes use the terms "domain" and "range" when we're talking about procedures, although technically, only functions have domains and ranges. Everybody that hears me sing iteither it brings the tears into their eyes, or else" "Or else what? The name of the song is called 'Haddock's Eyes. The name really is 'The Aged Aged Man. The song is called 'Ways And Means': but that's only what it's called, you know! Notice that when we defined the square procedure we gave a name, x, for its argument.
By contrast, when we invoked square we provided a value for the argument e. The word x is a "place holder" in the definition that stands for whatever value you use when you call the procedure. So you can read the definition of square as saying, "In order to square a number, multiply that number by that number. Be sure you understand this distinction between defining a procedure and calling it. A procedure represents a general technique that can be applied to many specific cases. We don't want to build any particular case into the procedure definition; we want the definition to express the general nature of the technique.
You wouldn't want a procedure that only knew how to take the square of 7. But when you actually get around to using square, you have to be specific about which number you're squaring. The name for the name of an argument whew! In our square example, x is the formal parameter. You may hear people say either "formal" alone or "parameter" alone when they're feeling lazy.
The technical term for the actual value of the argument is the actual argument. Most of the time it's perfectly clear what you mean, and you just say. The square procedure takes one argument. If a procedure requires more than one argument, then the question arises, which actual argument goes with which formal parameter?
Procedure as Generalization What's the average of 17 and 25? To answer this question you could add the two numbers, getting 42, and divide that by two, getting This is an example of what we meant when we defined "abstraction" as noticing a pattern and giving it a name. It's not so different from the naming of such patterns in English; when someone invented the name "average" it was, probably, after noticing that it was often useful to find the value halfway between two other values.
This naming process is more important than it sounds, because once we have a name for some idea, we can use that idea without thinking about its pieces. For example, suppose that you want to know not only the average of some numbers but also a measure of whether the numbers are clumped together close to the average, or widely spread out. Statisticians have developed the "standard deviation" as a measure of this second property.
You'd rather not have to think about this mysterious formula:. After all, there's no law of nature that says computers automatically know how to add or subtract. You could imagine having to instruct Scheme to compute the sum of two large numbers digit by digit, the way you did in elementary school. By inventing average or standard-deviation we are extending the repertoire of computations that you can ask for without concerning yourself with the details.
In particular, the rules for building expressions are the same whether the building blocks are primitive procedures or defined procedures. These small examples may seem arbitrary, but the same idea, composition of functions, is the basis for all Scheme programming. For example, the complicated formula we gave for standard deviation requires computing the squares of several numbers.
So if we were to write a standard-deviation procedure, it would invoke square. We're going to explain what happens when you invoke a user-defined procedure. Every explanation is a story. No story tells the entire truth, because there are always some details left out. A model is a story that has just enough detail to help you understand whatever it's trying to explain but not so much detail that you can't see the forest for the trees.
Today's story is about the substitution model. When a procedure is invoked, the goal is to carry out the computation described in its body. The problem is that the body is written in terms of the formal parameters, while the computation has to use the actual argument values. So what Scheme needs is a way to associate actual argument values with formal parameters.
You know, that's when you wave your hands around in the air instead of explaining what you mean. When you want to know the square of a particular number, as in square 5 , Scheme substitutes the 5 for x everywhere in the body of square and evaluates the expression. Only after the substitution does this become a meaningful expression. By the way, when we talk about "substituting into the body," we don't mean that the procedure's definition is changed in any permanent way.
The body of the procedure doesn't change; what happens, as we said before, is that Scheme constructs a new expression that looks like the body, except for the substitutions. The difference is that the little people who do primitive procedures can do the work "in their head," all at once. The little people who carry out user-defined procedures have to go through this substitution business we're talking about here. Then they hire other little people to help evaluate the resulting expression, just as Alonzo hires people to help him evaluate the expressions you type directly to Scheme.
Let's say Sam, a little person who specializes in square, has been asked to compute square 6. You may be thinking that this is rather an inefficient way to do thingsall this copying and replacement before you can actually compute anything. Perhaps you're afraid that your Scheme programs will run very slowly as a result. Don't worry. It really happens in a different way, but the effect is the same except for the speed. Sam then hires Tessa, a multiplication specialist, to evaluate this new expression.
Tessa tells Sam that her answer is 36, and, because the multiplication is the entire problem to be solved, this is Sam's answer also. Suppose Alonzo hires Harry to compute this expression. Now he evaluates that expression, just as Alonzo would evaluate it if you typed it at a Scheme prompt. Until we started defining our own procedures in this chapter, all of the little people were hired by Alonzo, because all expressions were typed directly to a Scheme prompt. Now expressions can come from the bodies of procedures, and so the little people needed to compute those expressions are hired by the little person who's computing that procedure.
Notice also that each little person reports to another little person, not necessarily the one who hired her. Only Shari reports directly to Harry. Don't forget, in the heady rush of learning about the substitution model, what you already knew from before: Each piece of this computation is done by a little person, and some other little person is waiting for the result.
In other words, the substitution model tells us how each compound procedure is carried out, but doesn't change our picture of the way in which procedure invocations are composed into larger expressions. Pitfalls Don't forget that a function can have only one return value. For example, here's a program that's supposed to return the sum of the squares of its two arguments: define sumofsquares x y square x square y ;; wrong!
The problem is that the body of this procedure has two expressions, instead of just one. As it turns out, Scheme just ignores the value of the first expression in cases like this, and returns the value of the last one. Another pitfall comes from thinking that a procedure call changes the value of a parameter. The area little person will substitute 8 for square everywhere in the procedure definition, leaving you with the expression 8 8 to evaluate. That expression would mean to apply the procedure 8 to the argument 8, but 8 isn't a procedure, so an error message results.
It isn't a problem if the formal parameter is the name of a procedure that you don't use inside the body. The problem arises when you try to use the same name, e.
But special forms are an exception; you can never use the name of a special form as a parameter. A similar problem about name conflicts comes up if you try to use a keyword the name of a special form, such as define as some other kind of nameeither a formal parameter or the name of a procedure you're defining. We're listing this separately because the result is likely to be different. Instead of getting the wrong value substituted, as above, you'll probably see a special error message along the lines of "improper use of keyword.
Remember that the job of the procedure definition is only to provide a name for the argument. The actual argument isn't pinned down until you invoke the procedure. People who write programs like the one above are trying to make the procedure definition do some of the job of the procedure invocation. Give their names, their specialties, their arguments, who hires them, and what they do with their answers. For each one, describe the function in English, show a sample invocation, and show the result of that invocation.
Real Exercises 4. Say what's wrong and why, and fix it:. The two formulas are 4. Do this two ways, first using the multiplication function, and then using square and not directly using multiplication. For example, 5 represents the number , while 3. A harder problem for hotshots: Can you write procedures that go in the other direction?
You might find the primitive procedures log and floor helpful. It should take the total bill as its argument and return the amount of the tip. Use the ceiling procedure to round up. That's because the discussions about evaluation and procedure definition were complicated enough without introducing extra ideas at the same time.
But now we're ready to get back to symbolic programming. As we mentioned in Chapter 3, everything that you type into Scheme is evaluated and the resulting value is printed out. Let's say you want to use ''square" as a word in your program. For example, you want your program to solve the problem, "Give me an adjective that describes Barry Manilow. Different versions of Scheme will have different ways of printing out procedures. What you need is a way to say that you want to use the word "square" itself, rather than the value of that word, as an expression. Quote is a special form, since its argument isn't evaluated.
Instead, it just returns the argument as is. Since Scheme uses the apostrophe as an abbreviation for quote, you can't use one as an ordinary punctuation mark in a sentence. That's why we've been avoiding titles like can't buy me love. To Scheme this would mean can quote t buy me love! What is a book? It's a bunch of pieces of paper, with printing on them, bound together.