Talking With Computers doesn't attempt to teach Scheme or any
other programming language. However, the ambitious reader or student
taking a class based on the book might be interested in more guidance
in learning the basics of programming in Scheme. In the class taught at
Brown, we spend a week (three lectures) learning some very basic
concepts and techniques for programming in Scheme. This isn't enough
to become proficient in Scheme, but it's enough to get started.
In the lectures, I borrow from two books: Felleisen, Findler, Flatt
and Krishnamurthi's How to Design
Programs [Felleisen et al.2001] (referred to as HTDP in the
lectures) is an excellent introduction to programming and I
particularly like the first four chapters for beginners. Abelson and
Sussman's Structure and Interpretation of Computer
Programs [Abelson and
Sussman1996] (referred to as SICP in the
lectures) is a little more advanced in places but has a wealth of
information and lots of interesting exercises.
Each book has an extensive web site
(the SICP web site
and the HTDP web site) containing useful
information for beginning and advanced programmers and each web site
includes a link to the full text
(the SICP
full text and the HTDP
full text).
You'll also find links to various implementations of Scheme on each web site.
I recommend DrScheme implementation
from PLT Scheme for beginner and
expert alike. DrScheme tips and tools are also integrated into the
HTDP web site and online version of the book.
We'll start with numbers and simple arithmetic functions. The
following interaction with Scheme illustrates a rough approximation of
Euler's constant (also called the natural logarithmic base), an
approximation of the area of a circle of radius 5 (the
approximation is due to approximating pi), the length of the
hypotenuse of an isosceles right triangle whose base is 5, an
approximation of Euler's constant computed by Scheme ((exp
n) is Euler's constant raised to the nth power --
try (log (exp n)) for some integer n), 2
raised to the power of (exponent) 10, and the error resulting from an
attempt to divide by zero (try (log 0) to produce another type
of error).
> 2.72
2.72
> (* 3.14 5 5)
78.5
> (sqrt (+ (* 5 5) (* 5 5)))
7.0710678118654755
> (exp 1)
2.718281828459045
> (expt 2 10)
1024
> (/ 1 0)
/: division by zero
Why can Scheme represent 0.3333... exactly but Euler's constant
only approximately? The functions sqrt, exp, *,
+ and / are all built into Scheme. What other functions
might you expect to find in Scheme?
You can define your own constants and
functions easily in Scheme. Here we generalize the expressions above
to create functions that can be used over and over again.
> (define pi 3.1415926536)
> (define (area radius)
(* pi (square radius)))
> (define (square number)
(* number number))
> (area 5)
78.53981634
And building further, here's a general procedure for calculating the
hypotenuse of a right triangle which makes use of a function for
calculating the Euclidean distance between two points in the plane.
> (define (hypotenuse length-leg-1 length-leg-2)
(distance length-leg-1 0 0 length-leg-2))
> (define (distance x1 y1 x2 y2)
(sqrt (+ (square (- x1 x2)) (square (- y1 y2)))))
> (hypotenuse 5 5)
7.0710678118654755
For a more leisurely introduction to numbers and simple functions, I
recommend that you work
through Sections
2.1-2.4 in HTDP dealing with numbers, simple arithmetic expressions,
and defining variables and simple programs. Don't just read the text;
type the expressions to Scheme and see for yourself what happens.
To understand how Scheme evaluates arithmetic expressions and
expressions involving user-defined functions, fire up DrScheme, set
the language to Beginning Student, and experiment executing simple
programs using the step utility. The step utility
graphically illustrates the steps in the substitution
model described in Talking With
Computers.
As a first experiment, download
the file
containing the definitions for calculating the cost of carpeting
Anne's living room as described in Talking With Computers and
check to see that the substitution steps outlined in the book match
those of DrScheme.
As another experiment, download
the file
containing the program for calculating the hypotenuse of a right
triangle and make sure you understand what's going on in this program.
If you want to learn a more about the substitution model, you might
check
out Section
1.1.5 of SICP. In
addition, Section
3.1-3.2 of HTDP provides guidance on composing functions to create
more complicated programs.
Computer programs are all about making choices to guide computations
and conditionals are the basic means to providing such guidance. The
simplest conditions consist of arithmetic relations, e.g., is one
number less than (<), greater than (>), or equal
(=) to another number. Simple expressions like (> x
y) evaluate to truth values which in Scheme are expressed as
#t for true and #f for false. These simple conditions
can then be composed into more complicated expressions using
truth-functional operators like and, or and not.
> (> 3 2)
#t
> (and (> 3 2) (< 1 4))
#t
> (not (> 3 2))
#f
> (or (> (+ 1 1 1) 5) (= (/ 6 3) 2))
#t
Now that you can specify various conditions, you want to be able to
make decisions on the basis of the truth or falsity of those
conditions. That's where conditional statements come in. The
simplest conditional statements are if-then-else statements. The else
part of a conditional statements is not required. You might
experiment to see what happens in a conditional statement with no else
part in which the condition evaluates to false. When would you use a
conditional statement that has no else part? Note that if-then-else
statements can be nested.
> (if (> 3 2) 1 0)
1
> (if (< 3 2) 0 (* 5 5))
25
> (if (> 3 2) (if (< 1 2) 1 2) 3)
1
Section
3.1-3.3 in HTDP emphasizes arithmetic relations,
truth-functional operators and conditionals. Instead of using the
if-then-else syntax, HTDP focuses on a more general conditional
statement illustrated by the following exchange.
> (define (absolute-value x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))
> (absolute-value 0)
0
> (absolute-value 3.14)
3.14
> (absolute-value -2.72)
2.72
Of course, absolute-value could have been defined more concisely as
(if (< x 0) (- x) x), but cond is handy for cases in which
nested if-then-else statements are cumbersome. Think about using cond
to assign letter grades to numeric scores.
You can do a lot with arithmetic relations and functions,
truth-functional operators, and conditional statements, but sooner or
later you'll want to add a little structure to your programs and
create abstractions of your data. For example, it makes sense to
think of a point in two-dimensional Euclidean space as a pair of
numbers corresponding to the point's x and y coordinates. Here's
how you'd realize that abstraction in Scheme.
> (define-struct point (x y))
> (define p1 (make-point 1 0))
> (define p2 (make-point 0 1))
> (define (distance point-1 point-2)
(sqrt (+ (square (- (point-x point-1)
(point-x point-2)))
(square (- (point-y point-1)
(point-y point-2))))))
> (distance p1 p2)
1.4142135623730951
You can use data structures like the one above to compose all sorts of
information. Data structures are often composed of other data
structures. Imagine a data structure used for keeping track of a
window on a computer screen. You'd need to keep track of the location
of the window on the screen -- a point of the sort described above
might work for this, the height and width of the window, and possibly
information about the colors, fonts, characters and graphics displayed
in the window.
There are also more primitive data structures that can be used to
build more complicated data structures. One such data structure is
the list which can be used to arrange and keep track of arbitrary
amounts of data. Lists appear in most programming languages
(including shell languages) and are useful for all sorts of tasks.
Here's a little taste of what you can do with lists in Scheme.
You can use the function list to create lists and the functions
car and cdr to access their contents. For our purposes,
the function car takes a single argument corresponding to a
list and returns the first item in the list. Similarly the function
cdr takes a list and returns the list consisting of the
remaining items in the list (minus the first item). These function
names are so inscrutable that often programmers define the functions
first and rest as we've done below. These functions are
already part of DrScheme when using the Beginning Student language.
They are not, however, part of standard Scheme. The function
cons can be used to construct new lists out of existing
lists. the invocation (cons item alist)
creates a new list whose first is item and whose
rest is alist.
> (define (first alist) (car alist))
> (define (rest alist) (cdr alist))
> (define nums (list 1 2 3 4))
> (first nums)
1
> (rest nums)
(2 3 4)
> (rest (rest nums))
(3 4)
> (+ (first nums) (first (rest (rest nums))))
4
> (define nest (list 1 (2 3) 4))
> (first nest)
1
> (first (rest nest))
(2 3)
> (first (first (rest nest)))
2
> (define more (cons 0 nums))
> (first more)
0
> (rest more)
(1 2 3 4)
Once you have lists and numbers you can create more complicated
mathematical entities like vectors and matrices. You can also use
lists to manage items other than numbers, like strings or composite
data structures like the point data structure described above. This
short introduction doesn't begin to cover what you can do with lists
or more generally with Scheme, but you'll find a much more complete
picture in HTDP and SICP. We'll also have more to say about lists as
we explore various applications in the book.
What's the big deal about computing?
I don't pretend that learning to program is easy. And I don't expect
that you will learn to be a good programmer from two weeks exposure.
But you can learn to think computationally without learning to be an
expert programmer. And computation is one of the ``big
ideas'' you'll encounter in your education.
What are some of the other so-called big ideas? Restricting our
attention to science, how about Galileo's idea that the planets
revolve about the sun, Newton's inverse square law, Hodgkin's idea to
use X-ray diffraction to analyze biological substances, Szilard's
insight concerning nuclear chain reactions, Darwin's notions about
natural selection, Mendel's genetic recombination, Einstein's
relativity, etc. Big ideas often correspond to rules that account for
observed events and allow us to predict new ones.
The inverse square law applies to gravitational forces, electric
fields, light, sound and radiation and can be used to explain (and
predict) all sorts of physical processes, e.g., the inverse square law
explains why it gets dark so fast as you move away from a
campfire. Sometimes big ideas provide us with a way of thinking about
a broad range of phenomena. For example, the integral and differential
calculus provides a basis for thinking about change over time whether
that change concerns the speed of projectiles or the populations of
predators and prey in a closed environment.
So what's the big idea about computation? It's the idea that
information can be mechanically manipulated according to a set of
rules in order to produce fundamentally new information that can be
used to transform the physical world and the way in which we perceive
it. In some sense, computation is the mother of all big ideas, the
motive force behind lawful behavior; some scientists like to think of
the universe as a big computer. Once you understand the basic ideas
surrounding computation, the implications are staggering.
Did you ever have a set of blocks, a doll house or a chemistry set
when you were a kid? What did you do when you played with these toys?
Explore, simulate and imagine all sorts of things? Today,
freely-available programming tools provide the basis for very
sophisticated explorations. It's like being given not just a set of
blocks but a construction company and a warehouse full of building
materials (think computer aided design); not just a little doll house
but a way to play with whole populations and explore complicated
social dynamics (think SimCity), not a
just cheap chemistry set with four small bottles of harmless chemicals
but a nuclear physics laboratory (check
out SourceForge for a listing of some
of the open-source software projects available on the web). As I
said, the implications are staggering, tremendously empowering and a
bit scary.
Why are there so many programming languages?
Computing is almost as generic as communicating. Specialists in
different disciplines may use a common base language to communicate
while at the same time employing very different specialized jargon and
technical terms. The basic syntax may seem familiar but the verbs and
nouns will have specialized meanings.
While it's true that programming languages differ in terms of their
syntax, e.g., Java doesn't look like Scheme, these differences are
often arbitrary and superficial. You could, for example, write a
program in C, Scheme or just about any other language, that would
transform the following Scheme program:
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
into a C or Java program that might look like
int factorial( int n ) {
int result;
if ( n == 0 )
result = 1;
else result = n * factorial( n - 1 );
return result;
}
Or the other way around. Using such a program you could write your
programs in one language and transform them into another language.
Why might you want to do this? Have you ever heard of esperanto? Do
you think there's a need for an esperanto for programming?
In some cases, the syntax of a language is designed to support a
particular way of thinking about computing. For example, Java and C++
are designed to support an object-oriented style of programming that
we'll explore in Chapters 6 and 7. However, you can
program in an object-oriented style in almost any language including
Scheme and in Chapter 7 we show how you can program in Scheme
using the same stylistic conventions as Java but using syntax that
looks a little more Scheme like.
What does it mean to debug a program?
Programs, like mechanical devices, can have design flaws that prevent
them from realizing their intended purpose. For example, in an
attempt to implement the factorial function, you might write a program
that gives the answer of 0 for the factorial of 0. That's the wrong
answer according
the standard
definition of factorial and a programmer might refer to this mistake
as a bug. Notice that this bug could be
the cause of other bugs if the buggy factorial function is used as
part of a larger program for, say, computing your taxes or controlling
a nuclear reactor.
The word debugging refers to eliminating
bugs in programs by rewriting code to avoid undesirable behavior.
Other bugs might cause programs to terminate prematurely (often with
nasty messages from the operating system) or not to terminate at all
(leaving you wondering what's going on).
The origin of the words ``bug'' and ``debugging'' used in the context
of computer programming is often traced to an event that occurred at
Harvard University early in the history of electronic computing
involving
a real
bug that caused a malfunction in the computer hardware. This
anecdote was a favorite
of Admiral Grace
Hopper who was at Harvard at the time and one of
the first computer programmers. Hopper is credited as the inventor of
the compiler which is a program that
translates programs written in one language into programs in another
language.
Is it ever the case that you write a program in one language and
inside that program you use another language?
It happens all the time. Here's a program written in HTML, a
formatting language very popular in constructimg web pages. This
program has embedded in it another program written in JavaScript, a
language used to make web pages more interactive. You can also embed
Scheme programs in HTML pages. Save this program to a file, e.g.,
script.html, use your browser to open
the file,
and then see what happens.
<HTML>
<BODY>
<SCRIPT language="JavaScript">
<!--
var secret_password = "yikes" ;
var answer = prompt("Type the secret password:","") ;
if (answer != secret_password) {
answer = prompt("Try again:","");
if (answer != secret_password) {
document.write("Sorry!<P>");
} else {
document.write("Got it that time!<P>");
}
} else {
document.write("You got it!<P>");
}
//-->
</SCRIPT>
</BODY>
</HTML>
Here's another HTML program. Embedded in this program are fragments
of yet another language called PHP that makes it possible for web
pages to call other programs (see Chapter 11 for more about how
the web works). In the program below, PHP is used to access and query
a MySQL database that contains information about artists and songs
(see the examples in Chapter 3), and then format the results of
the query in HTML so they can be displayed in a browser. The PHP code
actually generates the content of a web page. Notice that the PHP
code looks a lot like the C-shell programming language and that this
code issues queries using the MySQL database query language.
<HTML>
<BODY>
<?PHP
$db = mysql_connect("localhost", "root") ;
mysql_select_db("music", $db) ;
$result = mysql_query("SELECT last, birthdate FROM artist", $db) ;
echo "<TABLE BORDER=1>\n" ;
echo "<TR><TD>LAST NAME</TD><TD>BIRTHDATE</TD></TR>\n" ;
while ( $myrow = mysql_fetch_row($result) ) {
printf("<TR><TD>%s</TD><TD>%s</TD></TR>\n", $myrow[1], $myrow[2] ) ;
}
echo "</TABLE>\n" ;
?>
</BODY>
</HTML>
Here's what you'd see in a browser if you selected
this page
and here's what the resulting raw HTML code would look like:
<HTML>
<BODY>
<TABLE BORDER=1>
<TR><TD>LAST NAME</TD><TD>BIRTHDATE</TD>
<TR><TD>Frisell</TD><TD>1951-03-18</TD></TR>
<TR><TD>Raitt</TD><TD>1949-11-08</TD></TR>
<TR><TD>Taylor</TD><TD>1959-03-13</TD></TR>
<TR><TD>Cray</TD><TD>1953-08-01</TD></TR>
<TR><TD>Jarrett</TD><TD>1945-05-08</TD></TR>
<TR><TD>Foley</TD><TD>1968-03-29</TD></TR>
</TABLE>
</BODY>
</HTML>
Lisp is particularly good at dealing with symbolic data and, in
particular, with lists constructed from symbols, e.g., function and
variable names, and (recursively) other lists.
Think about how you would write the functions second,
third, fourth, etc. In this exercise, you are to
write a function that returns the nth item in a list.
Start by writing down a prose description of a recursive procedure to
accomplish this. Now implement your procedure in Scheme. Call the
procedure nth; it should perform so that (nth 3 (list 0
1 2 3)) returns 2.
Write down a description of a procedure to search a list for a
particular target item. Your procedure should return true if the
target is in the list and false otherwise. In writing this
procedure in Scheme, you'll probably want a general equality
predicate; = only works for numbers. Use DrScheme's help
utility to learn about equal? and then implement your search
procedure in Scheme using this predicate.
Think about a more sophisticated search procedure that works for
nested lists. This procedure would return true if the target is in
the list or (recursively) in any list contained in the list. Start
by thinking about the special case in which all lists have exactly
two elements.
Recursion isn't just good for math; it's an amazingly useful
tool for thinking about all sorts of complicated computations.
Here's a couple of examples that I adapted from
David Eck's The Most Complex Machine [Eck1995].
The first example involves drawing pictures that have a recursive
structure. Drawings of snowflakes are a good example. In order to
make drawings, we'll take advantage of graphics library in DrScheme
that allows us to emulate a programming language developed by
Seymour Papert to teach
children [Papert1980]. The language is
called Logo
and it was originally designed to allow kids to write programs to
control a small mobile robot called a turtle. In the
absence of a physical robotic turtle, most modern versions of Logo
control a simulated turtle that moves around in a graphics window
and can be used to draw (the original mechanical robots could
manipulate colored pens and thereby draw on paper). The version of
Logo available in DrScheme lets us move the turtle forward (a
positive integer) and backward (a negative integer), turn the
turtle (a specified number of degrees), and draw
lines. Here's
the code
to draw a diagram reminiscent of a snowflake:
(define (snowflake size depth)
(cond ((<= depth 1) (draw size))
(else (snowflake (/ size 2) (- depth 1))
(turn 90)
(snowflake (/ size 3) (- depth 2))
(turn 180)
(draw (/ size 3))
(snowflake (/ size 3) (- depth 2))
(turn 180)
(draw (/ size 3))
(turn -90)
(snowflake (/ size 2) (- depth 1)))))
And here's what the invocation (snowflake 500 8) produces in the
DrScheme graphics window:
Write a procedure using turn, move and draw to
produce a recursively structured drawing of your own design or a
design that you particularly like. For inspiration, you might search
for information on fractals and Benoit
Mandelbrot on the web.
In addition to drawing intricate recursively defined structures, we
can use recursion to capture some of the structure in languages.
The formal syntax or grammar of a natural or programming
language can be specified in terms of a set of recursive rules. The
follow procedure is one of several implementing a small fragment of
English. This procedure generates a sentence consisting of a noun
phrase followed by a verb phrase and possibly (in one out of seven
invocations on average) a conjunction and then another sentence.
(define (sentence)
(noun-phrase)
(verb-phrase)
(if (= 1 (random 7))
(and (conjunction)
(sentence))
(period)))
Like move, turn and draw in DrScheme's version
of Logo, the functions sentence, noun-phrase, and
period produce side effects which, in this case, result in
characters being displayed on your computer screen. In the
following exchange, I load the file containing
the code
and invoke sentence several times:
> (load "sentences.scm")
> (sentence)
katrina believes every hamster.
> (sentence)
the lemming believes tom but damien talks.
> (sentence)
some lemming who finds tom finds some hamster who believes the aardvark.
Alter the word choices and modify the procedures or add new ones to
create your own specialized language. Try to design it so that every
sentence generated makes some (albeit comical) sense.
In this exercise, we'll look at techniques for matching strings of
characters. In particular, we'll be interested in techniques for
approximate or fuzzy string matching. This might seem like a
pretty esoteric topic but string matching is important in looking up
information in databases, spelling correction, bioinformatics, and a
host of other applications in which exact matching is impossible or
inappropriate.
You already know about one techniques for fuzzy matching, namely using
grep or sed with regular expressions. For example, if
you want to look up Fred Neustein's name in your online address book,
but can only recall that his last name begins with an N and
ends with stein you can simply search using grep
"N.*stein" address.txt. Pattern matching using regular
expressions is so useful that most programming languages have one or
more libraries that support this functionality. MzScheme provides
built-in support for regular expression pattern matching using the
same pattern language as egrep. There is also a Scheme library
pregexp.ss that supports Perl-style regular expressions. In
the following, we'll use the built-in egrep-style functions.
Use the DrScheme Help Desk to learn about regular expressions and
the various functions for matching and replacing strings. Here's
how you'd use one such function regexp-match to handle the
problem of searching for Fred Neustein.
> (regexp-match "N.*stein" "Fred Neustein")
("Neustein")
Refine the above regular expression, so it will match Neustein or
Newstein but not Nathan Weinstein.
Scheme also permits reading from and writing to files. In Scheme
parlance, you open an input port for reading and
you open an output port for writing. You close a
port when you are finished reading or writing. While there are
separate functions for opening and closing ports, Scheme also offers
convenient procedures that simplify working with ports. The
procedure call-with-input-file takes the name of a file and a
procedure of one argument which is called with an input port opened
on the specified file. When this procedure completes, its result is
returned after closing the input port. If no file exists with the
indicated name, then call-with-input-file exits with an
error.
> (call-with-input-file "address.txt"
(lambda (input-port) (regexp-match "N.*stein" input-port)))
Create an address book called address.txt and experiment searching
for names using regular expressions.
Learn about call-with-output-file, read-line and
regexp-replace (regexp-replace*) and then use these
procedures to replace all occurrences of Java in a file with
Scheme.
There are times when you'd like to know how good a match is.
This is especially useful when you are dealing with strings that
might be corrupted in some way. This comes up in designing spelling
correction algorithms where the strings are corrupted by spelling
errors or in matching genetic data where the strings are corrupted
by mutations. For example if you have encounter the string
guord in a document did the author of the text mean to write
guard, gourd or possibly god or gar.
Various metrics have been devised to measure the
distance between two strings. For binary strings of
1s and 0s (called bits from the combination
of the words binary and digits),
the Hamming
distance is particularly useful. The
Hamming distance between two binary strings is the the number of
bits that differ between the two strings. You can also think of the
Hamming distance as the number of bits that need to be changed
(corrupted) to turn one string into the other.
Write a Scheme procedure that computes the Hamming distance between
two binary strings represented as lists of 1s and 0s.
Your procedure should exit with an appropriate error message if the
input is inappropriate, e.g., the lists are of different lengths or
contain items other than 1s and 0s. You can implement
your procedure any way that you want, but I suggest you consider
using apply along with the mapping functions map and
andmap for a simple and elegant solution.
Another useful distance metric is
the Levenshtein
distance also called the edit
distance. The Levenshtein distance between two strings of
characters is the the smallest number of insertions, deletions, and
substitutions required to change one string into the other. It is
used in biology to find similar sequences of nucleic acids in DNA or
amino acids in proteins. It is also used in spell checking and
machine translation applications. We're going to experiment with
a Scheme
implementation written by Neil W. Van Dyke. I'll assume you've
downloaded Van Dyke's code and saved it to a file
levenshtein.scm in your current working directory.
> (load "levenshtein.scm")
> (list-levenshtein '(g u o r d) '(g u a r d))
1
> (list-levenshtein '(g u o r d) '(g a r d))
2
> (list-levenshtein '(g u o r d) '(g o d))
2
Use a combination of regular expression pattern matching and Van
Dyke's implementation of Levenshtein distance to build a smart
lookup procedure for an address book. Van Dyke's implementation
includes a variant of list-levenshtein that works on strings.
> (string-levenshtein "guourd" "guard")
2
Your lookup procedure should work as follows: The user supplies a
name that he or she wants to lookup. Now you could compare the
user-supplied name with every name in the address book and then
choose the one or ones that are closest. Alternatively, you could
rank order the names by Levenshtein distance and then display top
ten ranked names. This technique might be a little slow if you have
a lot of names in your address book. Instead, I want you to first
use regular expression matching to find a set of plausible
candidates and then order them using Levenshtein distance. You can
devise your own technique for generating the list of candidate
names. One possibility is to start with a pattern that exactly
corresponds to the user-supplied name, e.g., "Neustein" and
then progressively relax the matching, e.g., from "N......n"
to "N.*n" to "N.*". You can achieve more control
matching by using the Perl-style routines in pregexp.ss.
> (require (lib "pregexp.ss"))
> (pregexp-match "N[a-z]{2,3}stein" "Nathan Weinstein")
#f
If you want to read more about fuzzy pattern matching, check out
the Metaphone
algorithm which is used to code English words phonetically by reducing
them to 16 consonant sounds. You might also find it interesting to
read about
the Soundex
algorithm which is used to code surnames phonetically by reducing them
to the first letter and up to three digits, where each digit is one of
six consonant sounds. The Soundex algorithm was devised to code names
recorded in US census records.
Humans are particularly good at pattern matching in text and
images. It's no wonder
that early work in Artificial Intelligence focused a good deal of
effort on pattern matching. Many of the
early automated
reasoning programs
and expert
systems relied on sophisticated pattern matching algorithms. In
this exercise, we'll take look at how pattern matching techniques
can be used to create computer personalities called
chatterbots.
In
1996, Joseph
Weizenbaum published a paper entitled ``ELIZA - A Computer Program
for the Study of Natural Language Communication Between Man and
Machine'' [Weizenbaum1966].14 Weizenbaum's ELIZA can carry
on a passable conversation with a human by matching user input against
a set of rules. Each rule consists of a pattern and a response
appropriate to any input matching the pattern. ELIZA's personality
depends on the set of rules provided; in Weizenbaum's paper, he
demonstrated a set of rules that enabled ELIZA to respond roughly as
would a Rogerian
psychotherapist. It was remarkable how believable the program was in
simulating human-like behavior; so believable in fact that some people
confided in the program as if it was a human therapist.15 For this exercise, I rewrote Peter Norvig's
implementation [Norvig1991] of ELIZA in Scheme (you can download
the code
in zip format):
> (load "eliza.scm")
> (eliza "TOM - ")
TOM - Hello Eliza.
ELIZA - I think I lost my mind.
TOM - Why do suspect this?
ELIZA - I have had a lobotomy.
Tom - That's terrible!
ELIZA - I feel disoriented.
TOM - I can imagine so.
Oops. I loaded the file containing the basic pattern recognition routines,
but it included only a very simple set of rules. To give ELIZA any
semblance of a human personality we'll have to add more rules:
TOM - Exit.
> (load "rules.scm")
> (eliza "TOM - ")
TOM - Hello.
ELIZA - How do you do. Please state your problem.
TOM - I feel frustrated.
ELIZA - Do you often feel frustrated?
TOM - Yes. Whenever I am rushed.
ELIZA - In what way are you rushed?
TOM - I have too much to do and too little time.
ELIZA - What does that suggest to you?
TOM - Perhaps I shouldn't take on so many things.
ELIZA - You do not seem quite certain!
TOM - Well, I could probably do more if I worked harder.
ELIZA - Really? If you worked harder!
TOM - Quit.
You can see how the program picks out pieces of my input and
incorporates them into its responses. Load the files as shown above
and try your hand interacting with ELIZA. Look carefully at the
rules in rules.scm and generate a session with ELIZA that
makes it look really dumb. Then see if you can generate a session
in which ELIZA responds cleverly.
Here's how you invoke the pattern matcher:
> (pattern-match '(?x ate ?y) '(John ate dinner))
((?y . dinner) (?x . John))
The function pattern-match returns a list of variable bindings
that can then be used to instantiate a response schema by substituting
that values in the bindings for the variables in the schema:
> (substitute (pattern-match '(?x ate ?y) '(John ate dinner)) '(Did ?x enjoy ?y))
(Did John enjoy dinner)
Create a pattern and response schema so that the inputs (3 * 3
= 9) and (5 * 5 = 25) produce (The number 3 squared is
9) and (The number 5 squared is 25)) respectively.
The function pattern-match should fail given your pattern and
the input (3 * 7 = 21).
Take a look at the code in eliza.scm and see if you
can figure out how the pattern matcher works. To help, you can load
verbose.scm, a version of eliza.scm that prints out
information on procedure calls and allows you to step through the
recursive invocations of pattern-match. At the prompt, enter
1 if you want to continue the step-by-step execution and
0 if you want to halt execution.
> (load "verbose.scm")
> (pattern-match '(?x ate ?y) '(John ate dinner))
Calling pattern-match.
Pattern: (?x ate ?y)
Input: (John ate dinner)
Bindings: ((t . t))
Continue (enter 0 or 1): 1
Calling pattern-match.
Pattern: ?x
Input: John
Bindings: ((t . t))
Continue (enter 0 or 1): 1
Calling variable-match with ?x and John.
Calling extend-bindings with ?x and John.
Calling pattern-match.
Pattern: (ate ?y)
Input: (ate dinner)
Bindings: ((?x . John))
Continue (enter 0 or 1): 1
Calling pattern-match.
Pattern: ate
Input: ate
Bindings: ((?x . John))
Continue (enter 0 or 1): 1
Calling pattern-match.
Pattern: (?y)
Input: (dinner)
Bindings: ((?x . John))
Continue (enter 0 or 1): 1
Calling pattern-match.
Pattern: ?y
Input: dinner
Bindings: ((?x . John))
Continue (enter 0 or 1): 1
Calling variable-match with ?y and dinner.
Calling extend-bindings with ?y and dinner.
Calling pattern-match.
Pattern: ()
Input: ()
Bindings: ((?y . dinner) (?x . John))
Continue (enter 0 or 1): 1
((?y . dinner) (?x . John))
Explain what happens when you try to match the pattern (?x ate
?y) against the input (Alice ate pizza and asparagus for
lunch).
Look at the code in eliza.scm and check out the functions
responsible for matching segment variables. Here is a
simple example showing how segment variables work:
> (pattern-match '((?* ?x) feel (?* ?y)) '(I can feel the difference))
Calling pattern-match.
Pattern: ((?* ?x) feel (?* ?y))
Input: (I can feel the difference)
Bindings: ((t . t))
Continue (enter 0 or 1): 1
Calling segment-match with start = 0.
Calling segment-match with position = 2.
Calling variable-match with ?x and (I can).
Calling extend-bindings with ?x and (I can).
Calling pattern-match.
Pattern: (feel (?* ?y))
Input: (feel the difference)
Bindings: ((?x I can))
Continue (enter 0 or 1): 1
Calling pattern-match.
Pattern: feel
Input: feel
Bindings: ((?x I can))
Continue (enter 0 or 1): 1
Calling pattern-match.
Pattern: ((?* ?y))
Input: (the difference)
Bindings: ((?x I can))
Continue (enter 0 or 1): 1
Calling segment-match with start = 0.
Calling variable-match with ?y and (the difference).
Calling extend-bindings with ?y and (the difference).
((?y the difference) (?x I can))
Now try to match the pattern ((?* ?x) I want (?* ?y))
against the input (I know I want to study psychoceramics).
Explain what happens.
Create a second set of rules for a character by the name of ALBERT
and then rewrite the eliza function so that ELIZA and ALBERT
can have a conversation together.
Download all the code fragments in this chapter as a
file in zip format.
![[home-Z-G-6.jpeg]](home-Z-G-6.jpeg)