% Module 1
% Basic Concepts
\documentclass[12pt,twoside]{article}
\usepackage{htx}

\me {Suzanne Menzel; menzel@cs.indiana.edu}
% Color of Document
\robinsEggBlue

\begin{document}

\docheader{Course C\\Programming Concepts}
{1} % Module Number
{The Mechanics of Program Writing} % Module Name

\begin{quote}
{\it There is no reason for any individual to have a computer in their
home.} 
\begin{quote}
{\small Ken Olson,\\
President (now retired) of Digital Equipment}
\end{quote}
\end{quote}

\hr

%% Goal List

\begin{goallist}
\item Students will use their problem solving skills to navigate a
specific programming environment. 

\item Students will interact with the {\bf Shakey the Robot}
\begin{gloss*}{applet} A Java program, which is linked into an HTML
document, then retrieved and executed using a Web browser.
\end{gloss*}, and understand the relationship between the 
\begin{gloss*}{program}
A series of instructions executed by the computer, one
after another. 
\end{gloss*} and
its behavior. 

\item Students will understand the concept of a program as a sequence
of statements in a particular language.

\item Students will understand what it means to run or execute a program.

\item Students will practice writing programs to direct Shakey
through specific tasks.

\item Students will understand the difference between 
\begin{gloss*}
{syntax} The syntax of a computer language specifies how words and
symbols can be combined into valid programs.  Another word for syntax
is {\it grammar}.
\end{gloss*}
and
\begin{gloss*}
{semantics} The semantics of a properly formed program statement
describes the {\it meaning} of the statement in plain English and how
it will be interpreted by the computer when it is executed.
\end{gloss*}
.

\item Students will understand how and why to use program 
\begin{gloss*}
{comments} Most programming languages provide a mechanism that allows
a programmer to embed documentation directly into a program.  Comments
provide additional information and explain special processing.  All
text within a comment is for the benefit of the human audience, and is
ignored by the computer.
\end{gloss*}
.

\item Students will understand the 
\begin{gloss*}
{debugging} Debugging is the removal errors, or bugs, from a computer
program.  It may take several attempts before all bugs are found and
eradicated, and its even possible to introduce new bugs while trying
to fix the old ones!
\end{gloss*}
process.

\end{goallist}

%% Prerequisites

\begin{prereqs}

\item Students must understand the STAIR problem solving process.

\item Students must have a basic understanding of computer 
\begin{gloss*}{hardware}
The tangible components of a computer system, such as the
keyboard, monitor, and circuit boards.
\end{gloss*}
and 
\begin{gloss*}{software}
Programs and data.
\end{gloss*}
.

\item Students should be familiar with a graphical web browser, such
as Netscape or Explorer. 

\end{prereqs}

\paleLavender
\section {Programs: Easy as Pie...}
%\image[left]{icons/trcherry.gif} % {\font{+2} \bf Easy as Pie...}

\hbox{
\parbox{3.5in}{\psfig{file=trcherry.ps}}
\hspace{3em}
\parbox{4.0in}{
You are a complex computing machine.  You carry out pre-programmed
instructions all the time.  For example, consider the process of
baking a cherry pie.  This is a well-known task that humans have been
doing for centuries.  Even if you don't know how to bake a cherry pie,
you do know that recipes for such a task exist.}}

\begin{figure}
%\image[center]{icons/trcherry.gif} 

{\it Ingredients:}

\begin{itemize}
\item 1 cup milk
\item 2 Tablespoons softened butter
\item $\frac{1}{4}$ teaspoon almond extract
\item 2 eggs
\item $\frac{1}{2}$ cup Bisquick
\item $\frac{1}{4}$ cup sugar
\item 1 can cherry pie filling (dark)
\item $\frac{1}{2}$ cup Bisquick
\item $\frac{1}{2}$ cup brown sugar
\item $\frac{1}{2}$ teaspoon cinnamon
\item 2 Tablespoons cold butter
\end{itemize}

{\it Directions:}

\begin{enumerate}
\item Heat oven to 400°F. 
\item Grease a 10" pie plate. 
\item Beat first 6 ingredients until smooth (about 15 seconds in blender or
1 minute with hand blender). 
\item Pour into pie plate. Spoon pie filling evenly over top. 
\item Bake for 25 minutes. 
\item Prepare streusel: cut butter into bisquick, brown sugar, and
cinnamon until crumbly. 
\item At end of 25 minutes baking time, top pie with streusel. 
\item Bake until streusel is brown, about 10 minutes longer. 
\item Cool before serving; refrigerate any remaining pie.
\end{enumerate}
\caption{Cherry Pie}
\label{chpie}
\end{figure}

\anchor{foobar}{Such} a recipe (see Figure~\ref{chpie})
consists of an ordered sequence of steps.  It's crucial to perform the
steps in the prescribed order.  It would not make sense to ``bake for
25 minutes'' before you've performed the ``heat oven to 400°F'' step.
But, if you follow the instructions carefully, you should be able to
produce a cherry pie at the end.  Note that there is a clear beginning
and end to this entire process.  Furthermore, note that you are
probably following a recipe that someone else invented and wrote down.
In computer science, we would say that you are {\it executing a
program} for baking a cherry pie.

Similarly, planning a task is a familiar process.  You want to bake a
cherry pie.  First, you search for a recipe.  Then you go shopping for
the ingredients.  Then you follow the recipe, wait for the pie to
cool, and, at long last, eat a big slice!  You came up with this
process on your own.  You didn't find it in a book.  You devised your
own program, and then executed it.  One step in your program involved
doing the actual baking, which meant following the instructions in the
recipe.  But, once that was accomplished, you pick up with the
``wait'' step of your program and continue.

So, planning a task is akin to {\it writing a program} and following a
recipe is akin to {\it executing or running a program}.  A program is
nothing more than a sequence of instructions, written by you or by
someone else.

\paleGreen
\section{Bugs and Miracles}
\psfig{file=bug.ps}
%\image[center]{icons/bug.gif} 

Suppose you located your recipe for cherry pie in a cookbook written
by Julia Child.  She, Julia Child, is the {\it programmer}.  She may
have tried several variations of her cherry pie program before she got
it just right.  Each time she had a new idea, she couldn't just
imagine what the results would be.  She actually had to bake a real
pie using her new idea.  That is, she had to execute her modified
program.  Then she had to test the result by tasting the pie.  Maybe
it was a good idea, and maybe it wasn't... maybe it had a {\it bug} in
it!  This process of refining a solution until it's correct is called
{\it debugging}.

Rather than planning tasks for people to perform, in this course you
will plan tasks for the computer to perform.  Furthermore, whereas
it's easy for us to make a mistake when following a recipe
(inadvertently skipping a step, or substituting salt for sugar), we
can safely assume that the computer will make no such errors.  If the
end product is not what we expect, then the mistake is with our
program, not with the computer itself.  

Finding errors in programs and correcting them is much of what
programming is all about.  In order to make your programming
experience as rewarding and painless as possible, and so you can have
the benefit of our experience, you will use a friendly environment for
developing your programs in this course.  Initially you will use an
environment for manipulating a simple robot.  Later, you will use a
more sophisticated environment, called Miracle, for creating
JavaScript programs.  These environments will, hopefully, guide you
through the process in a controlled way, so that you avoid many of the
most common pitfalls for beginning programmers.

\section {Communicating with Language}
%\image[center]{icons/conversa.gif} 

\hbox{
\parbox{2.7in}{\parskip 1ex
Julia Child wrote her cookbook in English, and that is why we can
understand and follow her directions.  If the cookbook had been in
French, at least some of us would have a hard time understanding what
to do.  

To program a computer we must first agree on a language that both we,
as programmers, and the computer understand.  A computer is not
sophisticated enough to understand a natural language like English or
French, so we must settle on one of many possible computer languages.
}
\hspace{1.5em}
\parbox{3.5in}{\psfig{file=conversa.ps}}
}
\vspace{1ex}

A computer is also not intelligent enough to make inferences about
what we mean if we don't use the proper grammer.  A native English
speaker can easily understand the meaning of this sentence ``I ain't
gonna go nowhere, nohow, not never.''  However, when we communicate
with the computer in the computer's language, we must use the proper
grammar at all times.  If we speak improperly, the computer will
simply inform us of our error and give up.  

\subsection {Syntax = Grammar}
\link{foobar}{To learn any new language}, one must not only learn the words and their
meanings, but also the rules describing how words can be combined to
form valid sentences.  The syntax of a language is a set of
rules governing the formation of grammatically correct sentences.  In a
natural language like German, one must understand the rules regarding
adjective endings and verb placement.  In a computer language, one
must understand the structure of each instruction and the proper use of
punctuation.

The sentences in a computer language are frequently called {\it
program statements}, and errors in the formation of statements,
i.e. grammatical errors, are called {\it syntax errors}.  A program
that contains one or more syntax errors will not execute.

For example, a simple declarative English sentence has the following
form:

\begin{center}
{\it article noun verb article noun }{\tt .}
\end{center}

If we agree that the word {\code the} is a particular instance of {\it
article}, {\code cat} and {\code milk} are instances of {\it noun}, and
{\code drinks} is an instance of {\it verb}, then the sentence

\begin{center}
{\code The cat drinks the milk.}
\end{center}

is syntactically correct.  So is

\begin{center}
{\code The milk drinks the cat.}
\end{center}

It's certainly true that the computer which is our brain would be
quite confused if we heard the above sentence.  Our brain does not
reject the sentence based on improper syntax, but rather on what we
know about the meanings of the individual words in the sentence.

\begin{quest}
Which of the following sentences contain one or more syntax errors
based on the grammatical rule above?

\begin{enumerate}
\item {\code The cat drinks the milk}
\item {\code The drinks milk cat the.}
\item {\code The cat drinks milk.}
\end{enumerate}

\end{quest}

Punctuation is an important part of the syntax of a computer language,
and it must be used properly.  Common punctuation symbols are ${\code
\{}$, ${\code \}}$, {\code (}, {\code )}, {\code "}, and {\code ;}.

\subsection{Semantics = Meaning}
A statement can be properly formed, yet produce an improper meaning,
as with the sentence {\code The milk drinks the cat.}  The meanings
assigned to the words in a language compise its {\it semantics}.
Errors in the meaning of statements are called, not surprisingly, {\it
semantic errors}.  A program that contains one or more semantic errors
will not produce the desired results.  The program will execute, but
it may stop unexpectedly at some point or it may run to completion but
yield an incorrect result.  

Going back to our cherry pie example, if we accidently use salt
instead of sugar, then we eventually get a pie at the end.  It looks
good, but when we taste it, we realize that something went wrong
during the execution of the recipe program.  On the other hand, if
Julia Child neglected to mention that we needed cinnamon in the list
of ingredients, then when we get to the step that tells us to add the
cinnamon, we would have to stop immediately and proceed no further
because we don't have any cinnamon in the house.  In this case, we
don't get a pie at the end.

Semantic errors are only detected during or after the program
execution, and so are also called {\it run-time errors}.

\section {Robots, Real and Imagined}
%\image[left]{icons/stiqicon.gif}

The most famous real-life robot in recent memory is probably
\xlink{http://mpfwww.jpl.nasa.gov/rover/sojourner.html}
{the Sojourner rover}, part of the
\xlink{http://mpfwww.jpl.nasa.gov}
{Mars Pathfinder Mission}, built by NASA and sent to Mars to travel
its uncharted, pathless surface in Summer 1997.  In 1992, Indiana
University's own
\xlink{http://www.cs.indiana.edu/hyplan/jwmills.html}
{Professor Jonathan Mills} invented
\xlink{http://www.computer.org/cspress/catalog/bp07408.htm}
{Stiquito}: a simple, inexpensive, six-legged
walking robot.  Professor Mills envisions one day possibly sending off
a group of 1000 or more of these small, insect-like robots into outer
space.  For more current information about the world of robotics, 
check out the links on
\xlink{http://ranier.hq.nasa.gov/telerobotics\_page/coolrobots.html}
{the cool robots page}.

{\centering\parbox{4in}{\psfig{file=stiqicon.ps}}\par}

%\image[left]{icons/north_trans.gif}

We start our journey into programming by writing programs to direct
an imaginary robot, named Shakey, through some simple tasks.  Shakey
lives on a fixed size grid, surrounded on all sides by a high fence.
Besides Shakey himself, there are two other types of objects that can
occupy his world.  The first type of object is a wall.  Walls are used
to represent obstacles that Shakey must maneuver around, such as
hurdles, mountains, enclosed rooms, and mazes.  The fence along the
perimeter is also composed of walls.

\vspace{1ex}
\hbox{
\parbox{2in}{\psfig{file=north_trans.ps}}\hspace{2em}
\parbox{4.85in}{\parskip 1ex
The second type of object in Shakey's world is an item.  Shakey is
equipped with a mechanical arm that he can use to pick up and put down
items.  Some of Shakey's tasks involve picking up or putting down
patterns made from items, or finding and transporting items.

Whenever we want Shakey to carry out a task in his world, we must
supply him with a program, that is, a detailed set of instructions
that describes how to perform the task.  Shakey can receive, memorize,
and execute such a program, assuming that it is written in a language
he can understand.
}}
\vspace{1ex}

The program can be saved in a file, to be later recalled and executed
again and again.  This is very similar to the redial feature found on
most telephones -- a number is recorded and then played back later (as
many times as is desired) at the touch of a button.

\subsubsection{Acknowledgement}
Much of this material on Shakey was inspired by {\it Karel the Robot}.
The definitive source for information about Karel is the book {\it
Karel the Robot, a gentle introduction to the art of programming}, by
Richard E. Pattis, second edition with revisions by Jim Roberts and
Mark Stehlik, published by John Wiley and Sons, 1995.

There is also an object-oriented version called 
\xlink{http://csis.pace.edu/$\tilde{\ }$bergin/karel.html}
{\it Karel++}.

\subsection {Shakey's Language}
Shakey understands the following six commands:

\begin{enumerate}
\item {\code step}:  When Shakey executes a {\code step} instruction, he
moves forward one square on his grid, continuing to face in the same
direction as before.  Shakey's program will terminate with a run-time
error if he is ever directed to step into a wall.  He may occupy the
same square as an item.

\item {\code left}:  Shakey executes a {\code left} instruction by
pivoting 90 degrees to the left, remaining on the same square.

\item {\code right}: Shakey executes a {\code right} instruction by
pivoting 90 degrees to the right, remaining on the same square.
 
\item {\code pickup}: Shakey picks up an item from the square he is
standing on.  If he executes a {\code pickup} instruction and the square
he is standing on does not contain an item, then his program
terminates with a run-time error.
  
\item {\code drop}:  Shakey places one item on the currently occupied
square.  If he is not carrying any items, or if the current square
already contains an item, then his program terminates with a run-time
error. 

\item {\code home}:  Shakey moves directly to his home position.  He
does not pass go... he does not collect 200 dollars.  (Ordinarily,
Shakey's home position is in the upper left hand corner of his grid,
facing north.)
\end{enumerate}

There is no limit to the number of items that Shakey can carry at one
time.

These six commands constitute the core of Shakey's language.  Later,
you will see how to extend the language by using these six commands as
building blocks.  Because they form the foundation of the language,
they are sometimes called {\it primitives}.

\subsection {Syntax of a Shakey Program}
A Shakey program contains a sequence of Shakey commands.  When
a Shakey program is run, he performs each command, one after the
other, in the order given.

When you use the programming environment to construct your program,
the text window will display the program that you are creating.
You do not have to actually type each program statement yourself.
Thus, you do not have to be overly concerned about the precise syntax
of Shakey's language.  However, you will see the text of your program
and you should be able to recognize the different statements and know
what they do.

Here is the syntax of each Shakey command:

\begin{verbatim}
command-name();
\end{verbatim}

The trailing punctuation after the command name is required, just as
the period must appear at the end of an English sentence.  

For example, the following sequence of instructions could be part of a
Shakey program.

\begin{verbatim}
step();
left();
drop();
\end{verbatim}

All of the statements that comprise the program are surrounded by
curly braces, {\tt \{} and {\tt \}}, and there is a header to the
program of the form:

\begin{verbatim}
function main()
\end{verbatim}

Here is an example of a complete Shakey program that will cause him to
turn right, take two steps, drop an item, and then return to his
original position:

\begin{verbatim}
function main() {
  right();
  step();
  step();

  drop();
  right();
  right();

  step();
  step();
  left();
}
\end{verbatim}

\subsection{Formatting Details}
For readability, we will put only one command on a single line, and
each command will be indented slightly.  Lines can be left entirely
blank, and we will do so frequently in our examples to show which
parts of the program hang together logically.

You must use all lower case letters in the command names.  The command
is {\code step}, not {\code Step} or {\code STEP}.

\subsection {Comments = Documentation}
Although Shakey will be carrying out the instructions in your program,
humans may also read the code you write.  Naturally, this includes your
instructor, but it also includes you yourself.  Consequently, the
language allows us to insert annotations within the code.  These
annotations are called 
\begin{gloss*}
{{\it comments}}
Most programming languages provide a mechanism that allows a programmer
to embed documentation directly into a program.  Comments provide additional
information and explain special processing.  All text within a comment
is for the benefit of the human audience, and is ignored by the computer.
\end{gloss*}
, and they are completely overlooked by Shakey.  Comments serve to
explain the intended logic of the program to the human audience.  

In Shakey's language, any text following the symbols {\code //} on a
line designates a comment.  For example:

\begin{verbatim}
// Take two steps and turn left.

step();  // first step
step();  // second step

left();  // turn
\end{verbatim}

The use of blank lines and comments makes your program easier for you
as the programmer to develop.  

\begin{quest}
In English, explain exactly what the following program fragment does.

\begin{verbatim}
left();
left();
step();
left();
left();
\end{verbatim}

\end{quest}

\subsection {Debugging Shakey Programs}
\vspace{1ex}
\begin{quote}
%\image[left]{icons/worf.jpg}
\hbox{
\parbox{3in}{\psfig{file=worf.ps}}\hspace{2em}
\parbox{5in}{
{\it Thank you, Lieutenant Woof.}\\
{\it It is WORF, madam!}
\begin{quote}
{\small Star Trek, The Next Generation}
\end{quote}}}
\end{quote}

There are two type of errors, or bugs, that can creep into your
program.  A {\it syntactic error} occurs when Shakey sees a word in his
program that is not part of his vocabulary.  If you inadvertently enter
{\code loft} instead of {\code left}, then the computer will not even
attempt to execute your program.  Instead you are presented with an
error message giving the nature and location of the bug.

Happily, the programming environment you will use insulates you from
such tedious syntactic bugs, since you do not actually type your
program yourself.  The program construction is carried out
automatically.  All you need to do is select the appropriate program
elements in the appropriate order.  Thus, you need not worry about
typos or forgetting punctuation.  You can concentrate on the more
important task of program
\begin{gloss*}
{design}
The plan for implementing a program, sometimes expressed using pseudocode.
\end{gloss*}
and correctness.

Assuming your program does not contain any syntactic errors (and it
won't if you construct it inside the programming environment), then the
computer will execute the program.  {\it Semantic errors} are mistakes
in the logic of the program, and emerge when the program is run.  For
example, it is a semantic error if you direct Shakey to step into a
wall at some point.

Just because Shakey successfully completes his program without any
error messages, does not mean that the program is error free.  Perhaps
he does not successfully complete his task.  Only you can judge
whether or not the result of running the program is correct.  For
example, suppose you want Shakey to jump three hurdles, but when your
program runs, he only jumps over two hurdles.  In that case, you must
go back and re-examine your logic, make corrections, and run the
program again.  This is analogous to tasting your cherry pie to see if
it turned out well. If it didn't, you must analyze your recipe to
determine what caused the failure.

Rarely is a program bug free on the first draft.  Debugging is the
main activity of even expert programmers.

\begin{lab*}
\subsection{Exploring the Shakey Environment}
\begin{exercise}
Shakey will do whatever you tell him to do, within his limited
abilities. 

Launch the Shakey applet and this is what you'll see.

%\image[center]{icons/screen.gif}
{\centering\parbox{4in}{\psfig{file=screen.ps,width=7in}}\par}

Click on the command buttons and see how Shakey reacts.  You should
see the corresponding instructions, along with descriptive comments,
appear in the text window.

Some actions will produce errors.  Try stepping Shakey into a wall, or
picking up an item from an empty square.  

\begin{quest}
What happens in the text window when Shakey encounters an error?  Is
the offending instruction included in the program?
\end{quest}
\end{exercise}

\subsection{Running a Shakey Program}
You have seen how to direct Shakey one instruction at a time.  If the
task to perform is long or complicated, it can be quite tedious to
repeatedly devise the correct instructions in this interactive
fashion.

It would be nice if we could develop the program just once, and then
execute it over and over again.

\begin{exercise}
Clear the window by selecting ``Load'' and then ``Clear''.  Select
``New Program''.  Go through the sequence of commands to cause Shakey
to take two steps, drop an item, turn right, and step.  If you make a
mistake, simply start over.  When you are satisfied that the program
that appears in the text window is the correct solution for this
problem, clear the window and then select ``Run'' to execute the
program.

You may run the Shakey program as many times as you wish, but be sure
to clear the window first.

\begin{quest}
What happens if you forget to clear the window before running the
program?
\end{quest}

That was a very short program.  Now construct a longer program of
twenty or so instructions.  It doesn't matter what Shakey does... he
can just turn in circles...

You can change the speed at which a program executes by adjusting the
``Speed'' slider bar.  

\begin{quest}
Is it possible to change Shakey's speed during program execution?
\end{quest}

Try experimenting with the ``Suspend'' and ``Resume'' features of
``Run''.
\end{exercise}

\subsection{Running Hurdles}
\begin{exercise}
``Load'' allows you to initialize Shakey's grid to various predefined
patterns.  

Load the ``Hurdles'' world now.

%\image[center]{icons/screen-hurdles.gif}
{\centering\parbox{4in}{\psfig{file=screen-hurdles.ps,width=6in}}\par}

The walls represent vertical hurdles that Shakey, the track and field
star, is about to run.  At the top of each hurdle is a flag.

Try moving Shakey about this world.  

\begin{quest}
What happens if you try to step into a hurdle?
\end{quest}

\begin{quest}
Construct a program that will maneuver Shakey over the hurdles, one at
a time, and have him collect all the flags.  Shakey must land on the
ground after jumping over each hurdle... he is not strong enough to
jump over more than one hurdle at a time.
\end{quest}

Now you are ready to begin writing some programs on your own.
\end{exercise}

\subsection{Getting the Newspaper}
\begin{exercise}
Every morning Shakey is awakened in bed when his newspaper is thrown
onto the front porch of his house.  Program Shakey to retrieve his
paper and bring it back to bed with him.

The Newspaper world depicts an arial view of Shakey in the morning.

%\image[center]{icons/screen-newspaper.gif}
{\centering\parbox{4in}{\psfig{file=screen-newspaper.ps}}\par}

To get you started, here is a pseudocode solution.

\begin{verbatim}
  // Newspaper world loaded.
  // Leave the bedroom...
  // Go to the door...
  // Get the paper...
  // Return to bed...
\end{verbatim}
\end{exercise}

\subsection{Shakey Goes Shopping}
\begin{exercise}
On the way home from the supermarket, Shakey's shopping bag ripped at
the bottom, leaking a few important items.  The initial situation,
when Shakey discovered the leak, is represented in the Shopping world.

Program Shakey to pick up all the dropped items and then line them up
inside his house, as shown below:

%\image[center]{icons/screen-shopping.gif}
{\centering\parbox{4in}{\psfig{file=screen-shopping.ps}}\par}
\end{exercise}

\subsection{Bowling for Dollars}
\begin{exercise}
In his spare time, Shakey works as a pin-setter in the local bowling
alley.  If you load the Bowling world, then Shakey is positioned in
the middle of the window, holding ten bowling pins.  

Write a program that directs Shakey to place the pins in a triangle
shape, where the first row contains one pin, the second row contains
two pins, the third row contains three pins, and the forth row
contains four pins.  The pins on each row are separated by a blank
spot.

%\image[center]{icons/screen-bowling.gif}
{\centering\parbox{4in}{\psfig{file=screen-bowling.ps}}\par}

Design your solution so that is can be easily extended.  That is, it
should be fairly easy to modify your program if, instead of ten pins,
Shakey started with fifteen pins and placed a fifth row of five pins
in the triangle.
\end{exercise}

\end{lab*}
\anslist{basicans.tex}
\cleardoublepage
\end{document}
