<P>
<P><A NAME="larson"></A>
<P><CENTER><IMG SRC="../ss-pics/farside.jpg" ALT="figure: farside"></CENTER>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 5: Words and Sentences</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 5</H2>
<H1>Words and Sentences</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/ssch05.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="../ssch4/defining.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch6/true.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>We started out, in Part I, with examples about acronyms and so on, but since
then we've been working with numbery old numbers. 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.
<P>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
<A NAME="g1"></A>Barry Manilow." If you just type <CODE>square</CODE> into Scheme, you
will find out that <CODE>square</CODE> is a procedure:
<P><PRE>> square
#<PROCEDURE>
</PRE>
<P>(Different versions of Scheme will have different ways of printing
out procedures.)
<P>What you need is a way to say that you want to use the word "<CODE>square</CODE>"
<EM>itself,</EM> rather than the <EM>value</EM> of that word, as an
expression. The way to do this is to use <A NAME="g2"></A><CODE>quote</CODE>:
<A NAME="spquote"></A>
<P><PRE>> (quote square)
SQUARE
> (quote (tomorrow never knows))
(TOMORROW NEVER KNOWS)
> (quote (things we said today))
(THINGS WE SAID TODAY)
</PRE>
<P><CODE>Quote</CODE> is a <A NAME="g3"></A><A NAME="g4"></A>special form, since its argument isn't evaluated.
Instead, it just returns the argument as is.
<P>Scheme programmers use <CODE>quote</CODE> a lot, so there is an abbreviation for it:
<P><PRE>> 'square
SQUARE
> '(old brown shoe)
(old brown shoe)
</PRE>
<P>(Since Scheme uses the apostrophe as an abbreviation for <CODE><A NAME="g5"></A>
quote</CODE>, you can't use one as an ordinary punctuation mark in a sentence.
That's why we've been avoiding titles like <CODE>(can't buy me love)</CODE>.
To Scheme this would mean <CODE>(can (quote t) buy me
love)</CODE>!)<A NAME="text1" HREF="words.html#ft1">[1]</A>
<P>This idea of quoting, although it may seem arbitrary in the context of
computer programming, is actually quite familiar from ordinary English.
What is a book? It's a bunch of pieces of paper, with printing on them,
bound together. What is "a book"? It's a noun phrase, made up of an article
and a noun. See? Similarly, what's 2+3? It's five. What's "2+3"?
It's an arithmetic formula. When you see words inside quotation marks, you
understand that you're supposed to think about the words themselves; you
don't evaluate what they mean. Scheme is the same way.
<P>(It's no accident that kids who make jokes like
<P><P><BLOCKQUOTE>Matt: "Say your name."
<P>Brian: "Your name."
<P></BLOCKQUOTE>
<P><P>grow up to be computer programmers. The difference between a
thing and its name is one of the important ideas that programmers need to
understand.)
<P><H2>Selectors</H2>
<P>So far all we've done with words and sentences is quote them. To do more
interesting work, we need tools for two kinds of operations: We have to be
able to take them apart, and we have to be able to put them
together.<A NAME="text2" HREF="words.html#ft2">[2]</A> We'll start with
the take-apart tools; the technical term for them is <EM>selectors.</EM>
<P><PRE>> (first 'something)
S
> (first '(eight days a week))
EIGHT
> (first 910)
9
> (last 'something)
G
> (last '(eight days a week))
WEEK
> (last 910)
0
> (butfirst 'something)
OMETHING
> (butfirst '(eight days a week))
(DAYS A WEEK)
> (butfirst 910)
10
> (butlast 'something)
SOMETHIN
> (butlast '(eight days a week))
(EIGHT DAYS A)
> (butlast 910)
91
</PRE>
<P>Notice that the <A NAME="g9"></A><CODE>first</CODE> of a sentence is a word, while the
<CODE>first</CODE> of a word is a letter. (But there's no separate data type
called "letter"; a letter is the same as a one-letter word.) The
<A NAME="g10"></A><CODE>butfirst</CODE> of a sentence is a sentence, and the <CODE>butfirst</CODE> of a
word is a word. The corresponding rules hold for <A NAME="g11"></A><CODE>last</CODE> and
<A NAME="g12"></A><CODE>butlast</CODE>.
<P>The names <CODE>butfirst</CODE> and <CODE>butlast</CODE> aren't meant to describe ways to
sled; they abbreviate "all <CODE>but</CODE> the <CODE>first</CODE>" and "all <CODE>but</CODE>
the <CODE>last</CODE>."
<P>You may be wondering why we're given ways to find the first and last
elements but not the 42nd element. It turns out that the ones we have are
enough, since we can use these primitive selectors to define others:
<P>
<PRE>(define (<A NAME="g13"></A>second thing)
(first (butfirst thing)))
> (second '(like dreamers do))
DREAMERS
> (second 'michelle)
I
</PRE>
<P>
<P>There is, however, a primitive selector <CODE>item</CODE> that takes
two arguments, a number <EM>n</EM> and a word or sentence, and returns the <EM>n</EM>th
element of the second argument.
<P>
<PRE>> (item 4 '(being for the benefit of mister kite!))
BENEFIT
> (item 4 'benefit)
E
</PRE>
<P>Don't forget that a sentence containing exactly one word is different from
the word itself, and selectors operate on the two differently:
<P>
<PRE>> (first 'because)
B
> (first '(because))
BECAUSE
</PRE>
<P>
<PRE>> (butfirst 'because)
ECAUSE
<A NAME="g14"></A><A NAME="g15"></A>> (butfirst '(because))
()
</PRE>
<P>The value of that last expression is the <EM>empty sentence.</EM> You can tell it's a sentence because of the
parentheses, and you can tell it's empty because there's nothing between
them.
<P><PRE>> (butfirst 'a)
""
> (butfirst 1024)
"024"
</PRE>
<P>As these examples show, sometimes <CODE>butfirst</CODE> returns a word
that has to have double-quote marks around it. The first example
shows the <EM><A NAME="g16"></A>empty word,</EM> while the second shows a number
that's not in its ordinary form. (Its numeric value is 24, but you don't
usually see a zero in front.)
<P><PRE>> 024
24
> "024"
"024"
</PRE>
<P>We're going to try to avoid printing these funny words. But don't
be surprised if you see one as the return value from one of the selectors
for words. (Notice that you don't have to put a single quote in front of
the double quotes. Strings are self-evaluating, just as numbers are.)
<A NAME="g17"></A>
<A NAME="g18"></A>
<A NAME="g19"></A>
<P>Since <CODE>butfirst</CODE> and <CODE>butlast</CODE> are so hard to type, there are
abbreviations <A NAME="g20"></A><CODE>bf</CODE> and <A NAME="g21"></A><CODE>bl</CODE>. You can figure out which is which.
<P><H2>Constructors</H2>
<P>Functions for putting things together are called <EM>constructors.</EM>
For now, we just have two of them: <A NAME="g22"></A><CODE>word</CODE> and <A NAME="g23"></A><CODE>sentence</CODE>. <CODE>Word</CODE> takes any number of words as arguments and joins them all together
into one humongous word:
<P><PRE>> (word 'ses 'qui 'pe 'da 'lian 'ism)
SESQUIPEDALIANISM
> (word 'now 'here)
NOWHERE
> (word 35 893)
35893
</PRE>
<P><CODE>Sentence</CODE> is similar, but slightly different, since it can take both
words and sentences as arguments:
<P><PRE>> (sentence 'carry 'that 'weight)
(CARRY THAT WEIGHT)
> (sentence '(john paul) '(george ringo))
(JOHN PAUL GEORGE RINGO)
</PRE>
<P><CODE>Sentence</CODE> is also too hard to type, so there's the
abbreviation <A NAME="g24"></A><CODE>se</CODE>.
<P><PRE>> (se '(one plus one) 'makes 2)
(ONE PLUS ONE MAKES 2)
</PRE>
<P>By the way, why did we have to quote <CODE>makes</CODE> in the last example, but
not <CODE>2</CODE>? It's because numbers are self-evaluating, as we said
<A NAME="g25"></A>
<A NAME="g26"></A>
in Chapter 3. We have to quote <CODE>makes</CODE> because otherwise Scheme
would look for something named <CODE>makes</CODE> instead of using the word
itself. But numbers can't be the names of things; they represent
themselves. (In fact, you could quote the <CODE>2</CODE> and it wouldn't make any
difference—do you see why?)
<P><H2>First-Class Words and Sentences</H2>
<P>If Scheme isn't your first programming language, you're probably accustomed
to dealing with English text on a computer quite differently. Many other
languages treat a sentence, for example, as simply a collection (a
"string") of <EM>characters</EM> such as letters, spaces, and punctuation.
Those languages don't help you maintain the two-level nature of English
text, in which a sentence is composed of words, and a word is composed of
letters.
<P>Historically, computers just dealt with numbers. You could add two numbers,
move a number from one place in the computer's memory to another place, and
so on. Since each instruction in the computer's native <EM>machine
language</EM> couldn't process anything larger than a number, programmers
developed the attitude that a single number is a "real thing" while
anything more complicated has to be considered as a collection of things,
rather than as a single thing in itself.
<P>The computer represents a text character as a single number. In many
programming languages, therefore, a character is a "real thing," but
a word or sentence is understood only as a collection of these
character-code numbers.
<P>But this isn't the way in which human beings normally think about their own
language. To you, a word isn't primarily a string of characters (although
it may temporarily seem like one if you're competing in a spelling bee).
It's more like a single unit of meaning. Similarly, a sentence is a
linguistic structure whose parts are words, not letters and spaces.
<P>A programming language should let you express your ideas in terms that match
<EM>your</EM> way of thinking, not the computer's way. Technically, we say
that words and sentences should be <EM>first-class data</EM> in our
language. This means that a sentence, for example, can be an argument to a
procedure; it can be the value returned by a procedure; we can give it a name;
and we can build aggregates whose elements are sentences. So far we've seen
how to do the first two of these. We'll finish the job in Chapter
7 (on <EM>variables</EM>) and Chapter 17 (on <EM>lists</EM>).
<P><H2>Pitfalls</H2>
<P>We've been avoiding apostrophes in our words and sentences because
they're abbreviations for the <CODE>quote</CODE> special form. You must also avoid
periods, commas, semicolons, quotation marks, vertical bars, and, of course,
parentheses, since all of these have special meanings in Scheme. You may,
however, use question marks and exclamation points.
<P>Although we've already mentioned the need to avoid names of primitives
when choosing formal parameters, we want to remind you specifically about the
names <CODE>word</CODE> and <CODE>sentence</CODE>. These are often very tempting formal
parameters, because many procedures have words or sentences as their
domains. Unfortunately, if you choose these names for parameters, you won't
be able to use the corresponding procedures within your definition.
<P><PRE>(define (plural word) ;; wrong!
(word word 's))
> (plural 'george)
ERROR: GEORGE isn't a procedure
</PRE>
<P>The result of substitution was not, as you might think,
<P><PRE>(word 'george 's)
</PRE>
<P>but rather
<P><PRE>('george 'george 's)
</PRE>
<P>We've been using <CODE>wd</CODE> and <CODE>sent</CODE> as formal parameters
instead of <CODE>word</CODE> and <CODE>sentence</CODE>, and we recommend that practice.
<P>There's a difference between a word and a single-word sentence. For
example, people often fall into the trap of thinking that the <CODE>butfirst</CODE>
of a two-word sentence such as <CODE>(sexy sadie)</CODE> is the second word, but it's
not. It's a one-word-long sentence. For example, its <CODE>count</CODE> is one,
not five.<A NAME="text3" HREF="words.html#ft3">[3]</A>
<P><PRE>> (bf '(sexy sadie))
(SADIE)
> (first (bf '(sexy sadie)))
SADIE
</PRE>
<P>We mentioned earlier that sometimes Scheme has to put double-quote marks
around words. Just ignore them; don't get upset if your procedure returns
<CODE>"6-of-hearts"</CODE> instead of just <CODE>6-of-hearts</CODE>.
<P><CODE>Quote</CODE> doesn't mean "print." Some people look at interactions
like this:
<P><PRE>> '(good night)
(GOOD NIGHT)
</PRE>
<P>and think that the quotation mark was an instruction telling
Scheme to print what comes after it. Actually, Scheme <EM>always</EM> prints
the value of each expression you type, as part of the read-eval-print loop.
In this case, the value of the entire expression is the subexpression that's
being quoted, namely, the sentence <CODE>(good night)</CODE>. That value wouldn't
be printed if the quotation were part of some larger expression:
<P><PRE>> (bf '(good night))
(NIGHT)
</PRE>
<P>If you see an error message like
<P><PRE>> (+ 3 (bf 1075))
ERROR: INVALID ARGUMENT TO +: "075"
</PRE>
<P>try entering the expression
<P><PRE>> (strings-are-numbers #t)
OKAY
</PRE>
<P>and try again. (The extension to Scheme that allows arithmetic
operations to work on nonstandard numbers like <CODE>"075"</CODE> makes ordinary
arithmetic slower than usual. So we've provided a way to turn the extension
on and off. Invoking <CODE>strings-are-numbers</CODE> with the argument <CODE>#f</CODE>
turns off the extension.)<A NAME="text4" HREF="words.html#ft4">[4]</A>
<P><H2>Boring Exercises</H2>
<P><B>5.1</B> What values are printed when you type these expressions to Scheme? (Figure
it out in your head before you try it on the computer.)
<P><PRE>(sentence 'I '(me mine))
(sentence '() '(is empty))
(word '23 '45)
(se '23 '45)
(bf 'a)
(bf '(aye))
(count (first '(maggie mae)))
(se "" '() "" '())
(count (se "" '() "" '()))
</PRE>
<P><B>5.2</B> For each of the following examples, write a procedure of two arguments
that, when applied to the sample arguments, returns the sample result.
Your procedures may not include any quoted data.
<P><PRE>> (f1 '(a b c) '(d e f))
(B C D E)
> (f2 '(a b c) '(d e f))
(B C D E AF)
> (f3 '(a b c) '(d e f))
(A B C A B C)
> (f4 '(a b c) '(d e f))
BE
</PRE>
<P>
<B>5.3</B> Explain the difference in meaning between <CODE>(first 'mezzanine)</CODE> and
<CODE>(first '(mezzanine))</CODE>.
<P>
<B>5.4</B> Explain the difference between the two expressions <CODE>(first (square 7))</CODE> and
<CODE>(first '(square 7))</CODE>.
<P>
<B>5.5</B> Explain the difference between <CODE>(word 'a 'b 'c)</CODE> and <CODE>(se 'a 'b 'c)</CODE>.
<P>
<B>5.6</B> Explain the difference between <CODE>(bf 'zabadak)</CODE> and <CODE>(butfirst
'zabadak)</CODE>.
<P>
<B>5.7</B> Explain the difference between <CODE>(bf 'x)</CODE> and <CODE>(butfirst '(x))</CODE>.
<P>
<B>5.8</B> Which of the following are legal Scheme sentences?
<P><PRE>(here, there and everywhere)
(help!)
(all i've got to do)
(you know my name (look up the number))
</PRE>
<P>
<B>5.9</B> Figure out what values each of the following will return <EM>before</EM>
you try them on the computer:
<P><PRE>(se (word (bl (bl (first '(make a))))
(bf (bf (last '(baseball mitt)))))
(word (first 'with) (bl (bl (bl (bl 'rigidly))))
(first 'held) (first (bf 'stitches))))
(se (word (bl (bl 'bring)) 'a (last 'clean))
(word (bl (last '(baseball hat))) (last 'for) (bl (bl 'very))
(last (first '(sunny days)))))
</PRE>
<P><B>5.10</B> What kinds of argument can you give <CODE>butfirst</CODE> so that it
returns a word? A sentence?
<P>
<B>5.11</B> What kinds of argument can you give <CODE>last</CODE> so that it returns a word? A
sentence?
<P>
<B>5.12</B> Which of the functions <CODE>first</CODE>, <CODE>last</CODE>, <CODE>butfirst</CODE>, and
<CODE>butlast</CODE> can return an empty word? For what arguments? What about
returning an empty sentence?
<P>
<H2>Real Exercises</H2>
<P><B>5.13</B> What does <CODE>'</CODE> <CODE>'banana</CODE> stand for?
<P>What is <CODE>(first '</CODE> <CODE>'banana)</CODE> and why?
<P>
<B>5.14</B> Write a procedure <CODE><A NAME="g27"></A>third</CODE> that selects the third letter of a word
(or the third word of a sentence).
<P>
<B>5.15</B> <A NAME="firsttwo"></A>
Write a procedure <CODE><A NAME="g28"></A>first-two</CODE> that takes a word as its argument,
returning a two-letter word containing the first two letters of the argument.
<P><PRE>> (first-two 'ambulatory)
AM
</PRE>
<P>
<B>5.16</B> Write a procedure <CODE><A NAME="g29"></A>two-first</CODE> that takes two words as arguments,
returning a two-letter word containing the first letters of the two
arguments.
<P><PRE>> (two-first 'brian 'epstein)
BE
</PRE>
<P>Now write a procedure <CODE><A NAME="g30"></A>two-first-sent</CODE> that takes a two-word
sentence as argument, returning a two-letter word containing the first
letters of the two words.
<P><PRE>> (two-first-sent '(brian epstein))
BE
</PRE>
<P>
<B>5.17</B> Write a procedure <CODE><A NAME="g31"></A>knight</CODE> that takes a person's name as its
argument and returns the name with "Sir" in front of it.
<P>
<P><PRE>> (knight '(david wessel))
(SIR DAVID WESSEL)
</PRE>
<P>
<B>5.18</B> Try the following and explain the result:
<P><PRE>(define (<A NAME="g32"></A>ends word)
(word (first word) (last word)))
> (ends 'john)
</PRE>
<P>
<B>5.19</B> Write a procedure <CODE><A NAME="g33"></A>insert-and</CODE> that takes a sentence of items and
returns a new sentence with an "and" in the right place:
<P><PRE>> (insert-and '(john bill wayne fred joey))
(JOHN BILL WAYNE FRED AND JOEY)
</PRE>
<P>
<B>5.20</B> Define a procedure to find somebody's middle names:
<P><PRE>
> (<A NAME="g34"></A>middle-names '(james paul mccartney))
(PAUL)
> (middle-names '(john ronald raoul tolkien))
(RONALD RAOUL)
> (middle-names '(bugs bunny))
()
> (middle-names '(peter blair denis bernard noone))
(BLAIR DENIS BERNARD)
</PRE>
<P>
<B>5.21</B> Write a procedure <CODE><A NAME="g35"></A>query</CODE> that turns a statement into a question
by swapping the first two words and adding a question mark to the last word:
<P><PRE>> (query '(you are experienced))
(ARE YOU EXPERIENCED?)
> (query '(i should have known better))
(SHOULD I HAVE KNOWN BETTER?)
</PRE>
<P>
<HR>
<A NAME="ft1" HREF="words.html#text1">[1]</A> Actually, it <EM>is</EM> possible to put punctuation
inside words as long as the entire word is enclosed in double-quote
marks, like this:
<A NAME="g6"></A>
<P><PRE>> '("can't" buy me love)
("can't" BUY ME LOVE)
</PRE>
<P>Words like that are called <EM>strings.</EM> We're not going
to use them in any examples until almost the end of the book. Stay away from
punctuation and you won't get in trouble. However, question marks and
exclamation points are okay. (Ordinary words, the ones that are neither
strings nor numbers, are officially called <EM>symbols.</EM>)<P>
<A NAME="ft2" HREF="words.html#text2">[2]</A><A NAME="g7"></A>
<A NAME="g8"></A> The procedures we're about to show you are not part of
standard, official Scheme. Scheme does provide ways to do these things, but
the regular ways are somewhat more complicated and error-prone for
beginners. We've provided a simpler way to do symbolic computing, using
ideas developed as part of the Logo programming language.<P>
<A NAME="ft3" HREF="words.html#text3">[3]</A> You met <CODE>count</CODE> in Chapter 2. It takes a word
or sentence as its argument, returning either the number of letters in the
word or the number of words in the sentence.<P>
<A NAME="ft4" HREF="words.html#text4">[4]</A> See Appendix A for a fuller explanation.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="../ssch4/defining.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch6/true.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>