\input bkmacs
% \photo{Scheme-Brained Hare}{\pagetag{\hare}\poop{Polly Jordan drawing}}
\photo{Scheme-Brained Hare}{\pagetag{\hare}
\pspicture{4in}{hare}{hare}{\TrimTop{60pt}\TrimRight{15pt}}}
\chapter{Showing Off Scheme}
\chaptag{\showing}

We are going to use the programming language Scheme to teach you some big
ideas in computer science.  The ideas are mostly about {\it
\bkidx{control of}{complexity}---\/}that 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 {\it 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 {\it \idx{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.)

\subhd{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 {\tt simply.scm}, which you need to make the
examples in this book work.

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:

{\prgex%
Welcome to XYZ Brand Scheme.
>
}

\noindent The {\tt >} is a {\it \idx{prompt},\/} Scheme's way of telling you
that it's ready for you to type something.  Scheme is an {\it interactive\/}
programming language.  In other words, you type a request to Scheme, then
Scheme prints the answer, and then you get another prompt.  Try it out:

{\prgex%
> \pmb{6}
6
}

\noindent We just asked Scheme, ``What is 6?'' and Scheme told us that 6 is
6.  Most of the time we ask harder questions:

{\prgex%
> \pmb{(+ 4 7)}
11
> \pmb{(- 23 5)}
18
> \pmb{(+ 5 6 7 8)}
26
}

\noindent Whenever something you type to Scheme is enclosed in parentheses,
\justidx{parentheses, for procedure invocation}
it indicates a request to carry out a {\it \idx{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 {\it \idx{argument}s,\/} i.e., values
that are used as data by the procedure.

Scheme has non-numeric procedures, too:

{\prgex%
> \pmb{(word 'comp 'uter)}
COMPUTER
}

\noindent (If this last example gives an error message saying
that Scheme doesn't understand the name {\tt word}, it means that you
didn't load the file {\tt simply.scm}.  Consult Appendix A.)

In these first examples, we've shown what you type in {\tt \pmb{boldface}} and
what the computer responds in {\tt lightface}.  Hereafter, we will rely on
the prompt characters to help you figure out who's talking on which line.

For the most part, Scheme doesn't care about whether you type in UPPER CASE
or lower case.  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.

\subhd{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,
{\tt ))))))}, and hitting the {\tt return} or {\tt 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
\justidx{error messages}
error.  Here's an example; for now, never mind exactly why this is an
error.  We just want to talk about the result:

{\prgex%
> (+ 2 a)

Unbound variable a
;Package: (user)

2 Error->
}

\noindent 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 {\it \idx{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.)

\vskip 12pt
% kludge to prevent repagination on last-minute 2/e fix.

\subhd{Exiting Scheme}

Although there's no official standard way to exit Scheme, most versions
use the notation

{\prgex%
> (\prgidx{exit})
}

\noindent for this purpose.  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.)

\subhd{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
work---it 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 {\tt first} and {\tt 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 {\it 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 {\it 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 {\tt 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.

\subhd{Example:\ Acronyms}

Here's our first new program.  So far we have just been using procedures
built into Scheme: {\tt +}, {\tt -}, and {\tt word}.  When you first start
up Scheme, it knows 100--200 procedures.  These are called {\it primitive\/}
\justidx{procedure, primitive}
\justidx{primitive procedure}
\justidx{procedure, compound}
\justidx{compound procedure}
procedures.  Programming in Scheme means defining new procedures, called
{\it compound\/} procedures.  Right now we're going to invent one that finds
the acronym for a title:

{\prgexskipamount=10pt\prgexbaselineamount=10.5pt
{\prgex%
(define (\ufun{acronym} phrase)
  (accumulate word (every first phrase)))

> (acronym '(american civil liberties union))
ACLU

> (acronym '(reduced instruction set computer))
RISC

> (acronym '(quod erat demonstrandum))
QED
}

Did you have trouble figuring out what all the pieces do in the {\tt
acronym} procedure?  Try these examples:

{\prgex%
> (first 'american)
A

> (every first '(american civil liberties union))
(A C L U)

> (accumulate word '(a c l u))
ACLU
}

Notice that this simple {\tt acronym} program doesn't always do exactly what
you might expect:

{\prgex%
> (acronym '(united states of america))
USOA
}

\noindent We can rewrite the program to leave out certain words:

{\prgex%
(define (\ufun{acronym} phrase)
  (accumulate word (every first (keep real-word? phrase))))

(define (\ufun{real-word?} wd)
  (not (member? wd '(a the an in of and for to with))))

> (acronym '(united states of america))
USA

> (acronym '(structure and interpretation of computer programs))
SICP

> (acronym '(association for computing machinery))
ACM

> (real-word? 'structure)
#T

> (real-word? 'of)
#F\pgfoot

> (keep real-word? '(united network command for law and enforcement))
(UNITED NETWORK COMMAND LAW ENFORCEMENT)
}
\vfootnt{In some versions of Scheme you might see {\tt ()} instead
of {\tt \#F}.}
} %%% skip kludge

\subhd{Example:\ Pig Latin}

Our next example translates a word into \bkidx{Pig}{Latin}.\footnt{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.}

\pagetag{\pig}
% \picture{1.9in}{Pig speaking Latin}
% ingualay atinalay orcinapay
\pspicture{1.9in}{pig}{pig}{\TrimBoundingBox{14pt}}

{\let\goodbreak=\relax\prgex%
(define (\ufun{pigl} wd)
  (if (member? (first wd) 'aeiou)
      (word wd 'ay)
      (pigl (word (butfirst wd) (first wd)))))

> (pigl 'spaghetti)
AGHETTISPAY

> (pigl 'ok)
OKAY
}\penalty10000\vskip 6pt
(By the way, if you've used other programming languages before, don't fall
\justidx{lines of a program}
into the trap of thinking that each line of the {\tt pigl} definition is a
``statement'' and that the\penalty-10000 statements\penalty-200\ are executed one after the other.
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 {\tt 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
\justidx{indentation in a program}
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.  If so, {\tt pigl} just adds
the letters {\tt ay} at the end:

{\prgex%
> (pigl 'elephant)
ELEPHANTAY
}

The following examples might make it a little more clear how the
starting-consonant case works:

{\prgex%
> (first 'spaghetti)
S

> (butfirst 'spaghetti)
PAGHETTI

> (word 'paghetti 's)
PAGHETTIS

> (define (\ufun{rotate} wd)
    (word (butfirst wd) (first wd)))

> (rotate 'spaghetti)
PAGHETTIS

> (rotate 'paghettis)
AGHETTISP

> (pigl 'aghettisp)
AGHETTISPAY
}

You've seen {\tt every} before, in the {\tt acronym} example, but we haven't
told you what it does.  Try to guess what Scheme will respond when you type
this:

{\prgex%
(every pigl '(the ballad of john and yoko))
}

\subhd{Example:\ Ice Cream Choices}

\vskip-2pt
Here's a somewhat more complicated program, but still pretty short
considering what it accomplishes:

\vskip-2pt
{\prgex\blskip8%
(define (\ufun{choices} menu)
  (if (null? menu)
      '(())
      (let ((smaller (choices (cdr menu))))
	(reduce append
		(map (lambda (item) (prepend-every item smaller))
		     (car menu))))))

(define (\ufun{prepend-every} item lst)
  (map (lambda (choice) (se item choice)) lst))

> (choices '((small medium large)
	     (vanilla (ultra chocolate) (rum raisin) ginger)
	     (cone cup)))
((SMALL VANILLA CONE)
 (SMALL VANILLA CUP)
 (SMALL ULTRA CHOCOLATE CONE)
 (SMALL ULTRA CHOCOLATE CUP)
 (SMALL RUM RAISIN CONE)
 (SMALL RUM RAISIN CUP)
 (SMALL GINGER CONE)
 (SMALL GINGER CUP)
 (MEDIUM VANILLA CONE)
 (MEDIUM VANILLA CUP)
 (MEDIUM ULTRA CHOCOLATE CONE)
 (MEDIUM ULTRA CHOCOLATE CUP)
 (MEDIUM RUM RAISIN CONE)
 (MEDIUM RUM RAISIN CUP)
 (MEDIUM GINGER CONE)
 (MEDIUM GINGER CUP)
 (LARGE VANILLA CONE)
 (LARGE VANILLA CUP)
 (LARGE ULTRA CHOCOLATE CONE)
 (LARGE ULTRA CHOCOLATE CUP)
 (LARGE RUM RAISIN CONE)
 (LARGE RUM RAISIN CUP)
 (LARGE GINGER CONE)
 (LARGE GINGER CUP))
}

\noindent 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 menu---try it out yourself.

\subhd{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.  ``Dozy, Beaky, and Tich'' counts as
the same team as ``Beaky, Tich, and Dozy''; the order within a team doesn't
matter.

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 \idx{algorithm}
yet.\footnt{What's an {\it 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 {\it sequential\/} nature of a recipe---first do
this, then do that, etc.  There can be more than one algorithm to solve the
same problem.} Instead, we just want you to marvel at Scheme's ability to
express difficult techniques succinctly.

{\prgex%
(define (\ufun{combinations} size set)
  (cond ((= size 0) '(()))
	((empty? set) '())
	(else (append (prepend-every (first set)
				     (combinations (- size 1)
						   (butfirst set)))
		      (combinations size (butfirst set))))))

> (combinations 3 '(a b c d e))
((A B C) (A B D) (A B E) (A C D) (A C E)
 (A D E) (B C D) (B C E) (B D E) (C D E))

> (combinations 2 '(john paul george ringo))
((JOHN PAUL) (JOHN GEORGE) (JOHN RINGO)
 (PAUL GEORGE) (PAUL RINGO) (GEORGE RINGO))
}

\noindent (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 {\tt A} and contain two more letters; the second group has
three letters not including {\tt 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 {\tt pigl} and {\tt acronym} procedures.)

If you've taken a probability course, you know that there is a formula for the
{\it 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 {\it symbolic\/} computing.  In this example,
listing the actual combinations instead of just counting them is part of the
flavor of \swapidx{symbolic}{computing}, along with our earlier examples about
\justidx{symbolic programming}
\justidx{programming, symbolic}
manipulating words and phrases.  We'll try to avoid numeric
problems when possible, because symbolic computing is more fun
for most people.

\subhd{Example:\ Factorial}

Scheme can handle numbers, too.  The \idx{factorial} of $n$ (usually written
in mathematical notation as $n!$) is the product of all the numbers from 1 to
$n$:
\justufun{factorial}

{\prgex\prgexpenalty=0%
(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

> (factorial 4)
24

> (factorial 1000)
4023872600770937735437024339230039857193748642107146325437999104299385
1239862902059204420848696940480047998861019719605863166687299480855890
1323829669944590997424504087073759918823627727188732519779505950995276
1208749754624970436014182780946464962910563938874378864873371191810458
2578364784997701247663288983595573543251318532395846307555740911426241
7474349347553428646576611667797396668820291207379143853719588249808126
8678383745597317461360853795345242215865932019280908782973084313928444
0328123155861103697680135730421616874760967587134831202547858932076716
9132448426236131412508780208000261683151027341827977704784635868170164
3650241536913982812648102130927612448963599287051149649754199093422215
6683257208082133318611681155361583654698404670897560290095053761647584
7728421889679646244945160765353408198901385442487984959953319101723355
5566021394503997362807501378376153071277619268490343526252000158885351
4733161170210396817592151090778801939317811419454525722386554146106289
2187960223838971476088506276862967146674697562911234082439208160153780
8898939645182632436716167621791689097799119037540312746222899880051954
4441428201218736174599264295658174662830295557029902432415318161721046
5832036786906117260158783520751516284225540265170483304226143974286933
0616908979684825901254583271682264580665267699586526822728070757813918
5817888965220816434834482599326604336766017699961283186078838615027946
5955131156552036093988180612138558600301435694527224206344631797460594
6825731037900840244324384656572450144028218852524709351906209290231364
9327349756551395872055965422874977401141334696271542284586237738753823
0483865688976461927383814900140767310446640259899490222221765904339901
8860185665264850617997023561938970178600408118897299183110211712298459
0164192106888438712185564612496079872290851929681937238864261483965738
2291123125024186649353143970137428531926649875337218940694281434118520
1580141233448280150513996942901534830776445690990731524332782882698646
0278986432113908350621709500259738986355427719674282224875758676575234
4220207573630569498825087968928162753848863396909959826280956121450994
8717012445164612603790293091208890869420285106401821543994571568059418
7274899809425474217358240106367740459574178516082923013535808184009699
6372524230560855903700624271243416909004153690105933983835777939410970
0277534720000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
}

\noindent If this doesn't work because your computer is too small, try a
more reasonably sized example, such as the factorial of 200.

\subhd{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 {\it 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.

\esubhd{Exercises}

{\exercise  Do 20 push-ups.}

{\exercise
Calculate 1000 factorial by hand and see if the computer got the right
answer.}

{\exercise
Create a file called {\tt acronym.scm} containing our acronym program, using
the text editor provided for use with your version of Scheme.  Load the file
into Scheme and run the program.  Produce a transcript file called {\tt
acronym.log}, showing your interaction with Scheme as you test the program
several times, and print it.
}

\bye