\input bkmacs
\photo{In a bucket brigade, each person hands a result to the
next.}{\pagetag{\bucket}\pspicture{4in}{bucket}{bucket}{\TrimBoundingBox{8pt}}}
\chapter{Expressions}
\chaptag{\people}

The interaction between you and Scheme is called the
``\idx{read-eval-print loop}.'' Scheme reads what you type, {\it evaluates\/}
it, and prints the answer, and then does the same thing over again.  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 {\it \idx{expression}.}\footnt{In
other programming languages, the name for what you type might be a
``command'' or an ``instruction.'' The name ``expression'' is meant to
emphasize that we are talking about the notation in which you ask the
question, as distinct from the idea in your head, just as in English you
express an idea in words.  Also, in Scheme we are more often asking
questions rather than telling the computer to take some action.} The
expression can be a single value, such as {\tt 26}, or something more
complicated in parentheses, such as {\tt (+ 14 7)}.  The first kind of
expression is called an {\it atom\/} (or {\it
\bkidx{atomic}{expression}\/}), while the second kind of expression is
called a {\it \bkidx{compound}{expression},\/} because it's made out of the
smaller expressions {\tt +}, {\tt 14}, and {\tt 7}.  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 {\it \idx{subexpression}s.}

Compound expressions tell Scheme to ``do'' a procedure.  This idea is so
important that it has a lot of names.  You can {\it call\/} a procedure; you
can {\it invoke\/} a procedure; or you can {\it 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 Scheme, everything is done by
calling procedures, just as we've been doing here.  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.  This sort of circularity comes up again and again
and again and again\footnt{and again} in Scheme programming.  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 {\it doesn't\/} have
smaller expressions inside it---the atomic expressions.

It's easy to understand an expression that just contains one number.
Numbers are {\it self-evaluating;\/} that is, when you evaluate a
\justidx{expression, self-evaluating}
\justidx{self-evaluating expression}
number, you just get the same number back.

Once you understand {\it numbers,\/} you can understand {\it expressions
that add up\/} numbers.  And once you understand {\it those\/} expressions,
you can use that knowledge to figure out {\it expressions that add up\/}
expressions-that-add-up-numbers.  Then \ellipsis\ and so on.  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
{\it any\/} expressions.''

{\advance\medskipamount by -3pt

So, for example, to understand the expression

{\prgex%
(+ (+ 2 3) (+ 4 5))
}

\noindent you must first understand {\tt 2} and {\tt 3} as self-evaluating
numbers, then understand {\tt (+~2~3)} as an expression that adds those
numbers, then understand how the sum, 5, contributes to the overall
expression.

} % medskipamount

By the way, in ordinary arithmetic you've gotten used to the idea that
parentheses can be optional; $3+4\times 5$ means the same as $3+(4\times 5)$.
But in Scheme, parentheses are {\it never\/} optional.  Every procedure call
must be enclosed in parentheses.

\subhd{Little People}

You may not have realized it, but inside your computer there are thousands
of \idx{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.

{\advance\medskipamount by -3pt

When you enter an expression, such as

{\prgex%
(- (+ 5 8) (+ 2 4))
}

\noindent Alonzo reads it, hires other little people to help him evaluate
it, and finally prints {\tt 7}, its value.  We're going to focus on the
evaluation step.

} % medskipamount

Three little people work together to evaluate the expression:\ a minus person
and two plus people.  (To make this account easier to read, we're using the
ordinary English words ``minus'' and ``plus'' to refer to the procedures
whose Scheme names are {\tt -} and {\tt +}.  Don't be confused by this and
try to type {\tt 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:

\medskip
{\parindent=1em
\bb 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.

\bb Alonzo looks at the subexpressions that should provide Alice's
arguments, namely, {\tt (+~5~8)} and {\tt (+~2~4)}.  Since both of these are
addition problems, Alonzo hires two plus specialists, Bernie and Cordelia,
and tells them to report their results to Alice.

\bb The first plus person, Bernie, also wants some numbers, so he asks
Alonzo for them.

\bb Alonzo looks at the subexpressions of {\tt (+~5~8)} that should provide
Bernie's arguments, namely, {\tt 5} and {\tt 8}.  Since these are both
atomic, Alonzo can give them directly to Bernie.

\bb Bernie adds his arguments, {\tt 5} and {\tt 8}, to get {\tt 13}.  He
does this in his head---we don't have to worry about how he knows how to
add; that's his job.

\bb The second plus person, Cordelia, wants some arguments; Alonzo looks at
the subexpressions of {\tt (+~2~4)} and gives the {\tt 2} and {\tt 4} to
Cordelia.  She adds them, getting {\tt 6}.

\bb Bernie and Cordelia hand their results to the waiting Alice, who can now
subtract them to get {\tt 7}.  She hands that result to Alonzo, who prints
it.

}\medskip

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 {\it \bkidx{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 {\it parallel
processing\/} computer.  However, it {\it is\/} important that both Bernie
and Cordelia finish their work before Alice can do hers.

The entire call to {\tt -} is itself a single expression; it could be a
part of an even larger expression:

{\prgex%
> (* (- (+ 5 8) (+ 2 4))
     (/ 10 2))
35
}

\noindent 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.
(By the way, we would say that the above expression has three
subexpressions, the {\tt *} and the two arguments.  The argument
subexpressions, in turn, have their own subexpressions.  However, these
sub-subexpressions, such as {\tt (+~5~8)}, don't count as
subexpressions of the whole thing.)

We can express this organization of little people more formally.  If
an expression is atomic, Scheme just knows the value.\footnt{We'll
explain this part in more detail later.} Otherwise, it is a compound
expression, so Scheme first evaluates all the subexpressions (in some
unspecified order) and then applies the value of the first one,
which had better be a procedure, to the values of the rest of them.
Those other subexpressions are the \idx{argument}s.

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.
Look at this long, messy example:
\justidx{parentheses, for procedure invocation}

{\advance\medskipamount by -1pt
{\prgex%
> (+ (* 2 (/ 14 7) 3)
     (/ (* (- (* 3 5) 3) (+ 1 1))
        (- (* 4 3) (* 3 2)))
     (- 15 18))
13
}

Scheme understands this by looking for the subexpressions of the overall
expression, like this:

{\prgex%
(+ (\ellipsis)
   (\ellipsis         ; One of them takes two lines but you can tell by
      \ellipsis)     ; matching parentheses that they're one expression.
   (\ellipsis))
}

\noindent (Scheme ignores everything to the right of a \idx{semicolon}, so
semicolons can be used to indicate \idx{comments}, as above.)

} % medskipamount

Notice that in the example above we asked {\tt +} to add {\it three\/}
numbers.  In the {\tt functions} program of Chapter~\functions\ we
pretended that every Scheme function accepts a fixed number of arguments,
but actually, some functions can accept any number.  These include {\tt +},
{\tt *}, {\tt word}, and {\tt sentence}.

\subhd{Result Replacement}

\justidx{result replacement}
\justidx{replacement, result}
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 {\it rewrite\/} it repeatedly,
each time replacing some small expression with a simpler expression
that has the same value.

{\prgex%
(+ (* \zboxit{(- 10 7)} (+ 4 1)) (- 15 (/ 12 3)) 17)
(+ (* 3        \zboxit{(+ 4 1)}) (- 15 (/ 12 3)) 17)
(+ \zboxit{(* 3        5      )} (- 15 (/ 12 3)) 17)
(+ 15                   (- 15 \zboxit{(/ 12 3)}) 17)
(+ 15                   \zboxit{(- 15 4       )} 17)
\zboxit{(+ 15                   11              17)}
43
}

\noindent 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 {\it several\/} small
expressions from one line to the next:

{\prgex%
(+ (* \zboxit{(- 10 7)} \zboxit{(+ 4 1)}) (- 15 \zboxit{(/ 12 3)}) 17)
(+ \zboxit{(* 3        5      )} \zboxit{(- 15 4       )} 17)
\zboxit{(+ 15                   11              17)}
43
}

\subhd{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
\justidx{function machine}
\justidx{machine, function}
ones they drew on the chalkboard in junior high school.  

\pspicture{1.4in}{function}{function}{}

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.'' Let's look at the \bkidx{plumbing}{diagram}
for {\tt (- (+ 5 8) (+ 2 4))}:
\pagetag{\crank}  %% Matt thinks this is a kludge but Brian...

\pspicture{2.5in}{Plumbing Diagram}{plumbing}{\TrimTop{0.5truein}}

You can annotate the diagram by indicating the actual information that flows
through each pipe.  Here's how that would look for this expression:

\pspicture{2.5in}{Annotated Plumbing Diagram}{annotated}{\TrimTop{0.5truein}
\TrimBottom{0.15truein}}

\subhd{Pitfalls}

\pit 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,

{\prgex%
(square (cos 3))
}

\noindent {\it doesn't\/} mean ``square three, then take the cosine of
the answer you get.'' Instead, as you know, it means that the argument to
{\tt square} is the return value from {\tt (cos~3)}.

\pit 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.  But to Scheme,
\justidx{indentation}

{\prgex%
(+ (* 2 (/ 14 7) 3) (/ (* (- (* 3 5) 3) (+ 1
1)) (- (* 4 3) (* 3 2))) (- 15 18))
}

\noindent means the same thing as

{\prgex%
(+ (* 2 (/ 14 7) 3)
   (/ (* (- (* 3 5) 3) (+ 1 1))
      (- (* 4 3) (* 3 2)))
   (- 15 18))
}

\noindent So in this expression:

{\prgex%
(+ (* 3 (sqrt 49)                            ;; weirdly formatted
   (/ 12 4)))
}

\noindent there aren't two arguments to {\tt +}, even though it looks that
way if you think about the indenting.  What Scheme does is look at the
parentheses, and if you examine these carefully, you'll see that there are
three arguments to {\tt *}:\ the atom {\tt 3}, the compound expression {\tt
(sqrt~49)}, and the compound expression {\tt (/~12~4)}.  (And there's only one
argument to {\tt +}.)

\pit 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.  This is fine if your program is
correct, but if you type this in:

{\prgex%
(+ (* 3 4)
   (/ 8 2)                              ; note missing right paren
}

\noindent then {\it nothing\/} will happen.  Even if you type forever, until
you close the open parenthesis next to the {\tt +} sign, Scheme will still
be reading an expression.  So if Scheme seems to be ignoring you, try typing
a zillion close \idx{parentheses}.  (You'll probably get an error message about
too many parentheses, but after that, Scheme should start paying attention
again.)

\pit You might get into the same sort of trouble if you have a double-quote
mark ({\tt "}) in your program.  Everything inside a pair of quotation marks
is treated as one single {\it \idx{string}.\/} We'll explain more about
strings later.  For now, if your program has a stray quotation mark, like
this:

{\prgex%
(+ (* 3 " 4)                            ; note extra quote mark
   (/ 8 2))
}

\noindent then you can get into the same predicament of typing and having
Scheme ignore you.  (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.)

\pit 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 {\tt return} or {\tt enter} key
without typing anything, most versions of Scheme won't print a new prompt.

\esubhd{Boring Exercises}

{\exercise
Translate the arithmetic expressions $(3+4) \times 5$ and $3+(4 \times 5)$
into Scheme expressions, and into plumbing diagrams.
}

\solution
$(3+4) \times 5$ becomes {\tt (*~(+~3~4)~5)} and $3+(4 \times 5)$ becomes
{\tt (+~3~(*~4~5))}.

Here are the plumbing diagrams:

\pspicture{1.5in}{Plumbing diagram}{ex3.1}{\TrimTop{0.5truein}}
@

{\exercise
How many little people does Alonzo hire in evaluating each
of the following expressions:
 
{\prgex%
(+ 3 (* 4 5) (- 10 4))
 
(+ (* (- (/ 8 2) 1) 5) 2)
 
(* (+ (- 3 (/ 4 2))
      (sin (* 3 2))
      (- 8 (sqrt 5)))
   (- (/ 2 3)
      4))
}}

\solution
The number of little people is equal to the number of functions invoked,
i.e., 3, 4, and 10 for the three examples.
@

{\exercise
Each of the expressions in the previous exercise is compound.  How many
subexpressions (not including subexpressions of subexpressions) does each
one have?

For example,

{\prgex%
(* (- 1 (+ 3 4)) 8)
}

\noindent has three subexpressions; you wouldn't count {\tt (+~3~4)}.
}

\solution
4, 3, and 3.  Remember that the name of the function is one of the
subexpressions!  So for the first expression the four
subexpressions are:

{\prgex%
+
3
(* 4 5)
(- 10 4)
}
@

 
{\exercise
Five little people are hired in evaluating the following expression:
 
{\prgex%
(+ (* 3 (- 4 7))
   (- 8 (- 3 5)))
}
 
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.  }

\solution
Working from inside out:

{\parskip=0pt\parindent=0pt
Marvin's specialty is {\tt -}, gets arguments {\tt 4} and {\tt 7}, returns
{\tt -3} to Tenar.

Tenar's specialty is {\tt *}, gets arguments {\tt 3} and {\tt -3}, returns
{\tt -9} to Piemur.

Malvina's specialty is {\tt -}, gets arguments {\tt 3} and {\tt 5}, returns
{\tt -2} to Manfred.

Manfred's specialty is {\tt -}, gets arguments {\tt 8} and {\tt -2}, returns
{\tt 10} to Piemur.

Piemur's specialty is {\tt +}, gets arguments {\tt -9} and {\tt 10}, returns
{\tt 1} to Alonzo.

}
@

{\exercise
Evaluate each of the following expressions using the result replacement
technique:

{\prgex%
(sqrt (+ 6 (* 5 2)))

(+ (+ (+ 1 2) 3) 4)
}
}

\solution
{\prgex%
(sqrt (+ 6 (* 5 2)))
(sqrt (+ 6 10))
(sqrt 16)
4

(+ (+ (+ 1 2) 3) 4)
(+ (+ 3 3) 4)
(+ 6 4)
10
}
@

{\exercise
Draw a plumbing diagram for each of the following expressions:
 
{\prgex%
(+ 3 4 5 6 7)
 
(+ (+ 3 4) (+ 5 6 7))
 
(+ (+ 3 (+ 4 5) 6) 7)
}}

\solution
\pspicture{1.5in}{Plumbing diagrams}{ex3.6}{\TrimTop{1.5truein}}
@

{\exercise
What value is returned by {\tt (/ 1 3)} in your version of
Scheme?  (Some Schemes return a decimal fraction like {\tt 0.33333}, while
others have exact fractional values like {\tt 1/3} built in.)
}

{\exercise
Which of the functions that you explored in Chapter \functions\ will
accept variable numbers of arguments?
}

\solution
All the following functions take an arbitrary number of arguments:
{\tt *}, {\tt +}, {\tt <=}, {\tt <}, {\tt =}, {\tt >=}, {\tt >}, {\tt and},
{\tt max}, {\tt min}, {\tt or}, {\tt sentence}, and {\tt word}.

Also, {\tt -} and {\tt /} take variable numbers of arguments in some
versions of Scheme.
@

\esubhd{Real Exercises}

{\exercise
The expression {\tt (+~8~2)} has the value {\tt 10}.  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:
 
\medskip
{\parindent=1em
\bb An atom

\bb Another compound expression made up of three atoms

\bb A compound expression made up of four atoms

\bb A compound expression made up of an atom and two compound subexpressions

\bb Any other kind of expression

}\medskip
}

\solution
{\parindent=1em
\bb {\tt 10} is the only possible answer.
\bb {\tt (+ 4 6)}, or any appropriate two-argument function with atomic
arguments.
\bb {\tt (+ 2 3 5)}, or any appropriate three-argument function with atomic
arguments.
\bb {\tt (* (+ 1 1) (- 9 4))}, or any two-argument function whose arguments
are provided by function calls.
\bb {\tt (sqrt 100)}, or many more complicated possibilities.

}
@

\bye