% Module 2
% Functions
\documentstyle{mmcc}
\me {Suzanne Menzel; menzel@cs.indiana.edu}
% Color of Document
\robinsEggBlue

\begin{document}

\docheader{Course C\\Programming Concepts}
{2} % Module Number
{Evolution} % Module Name

\begin{quote}
{\it There is nothing remarkable about it.  
\mkp*{BR}
All one has to do is hit the right keys \mkp*{BR}
at the right time, and the instrument plays itself.} 
\mkp*{BR}
{\font{-1} J.S. Bach}
\end{quote}

\mkp*{HR}

%% Goal List

\begin{goallist}
\item Students will understand how to extend a programming language by
defining their own 
\begin{gloss*}[function definition]
{functions}
A function definition is a subprogram, i.e. a collection of program
statements that, when {\it called}, performs some task.  Every such
subprogram is given a {\it name} by the programmer. This name
becomes a new command in the programming language and it is used just
like any of the other primitive commands in the language.

One can think about the collection of function definitions as a {\it
dictionary}.  When Shakey encounters a word that is not one of his
primitives, he then consults his dictionary.  If the word is in the
dictionary, then associated with the dictionary entry is the meaning
of the word.  Naturally, this meaning must be expressed in words that
Shakey already understands (i.e. the primitive commands) or words that
Shakey can look up in his dictionary (i.e. new user-defined
functions).
\end{gloss*}
.

\item Students will understand how to 
\begin{gloss*}[function call]
{call}
A function call is a statement that causes the execution of the
current function to be suspended.  Program control is then transferred
to the named function.  When that function terminates, the execution
of the calling function is resumed with the statement following the
function call.

All of the primitive commands in the Shakey language are function
calls.  Once you have defined your own functions, they can be called
using the same syntax as for the Shakey primitives.
\end{gloss*}
their own functions.

\item Students will understand the concept of a program as a
collection of subprograms (or functions).

\item Students will understand why functions are important and useful.

\item Students will understand how to break a problem into
subproblems.

\item Students will learn how to write readable and efficient code,
using functions.
\end{goallist}

%% Prerequisites

\begin{prereqs}

\item Students must understand the STAIR problem solving process.

\item Students must understand what a computer program is and what it
means to create and execute a program.

\item Students must be familiar with the basics of the Shakey
programming language and the Shakey programming environment.

\end{prereqs}

\paleLavender
\section* {Subprograms: Easy as Pie...}
\image[left]{icons/trcherry.gif} 

You want to make a cherry pie.  After consulting Julia Child, you
notice that one step in the recipe is given as:

\begin{itemize}
\item Prepare streusel: cut butter into bisquick, brown sugar, and
cinnamon until crumbly. 
\end{itemize}

Such concoctions are common toppings used in many cake and pie
recipes, not just recipies for cherry pie.  Over time, people got
tired of referring to it as ``that crumbly mixture of fat, sugar, and
flour'' and eventually gave it a name of its own: streusel.

New words are constantly being introduced into our language.  Some are
simply abbreviations, like ``NASDAQ'', and some are hybrids of two or
more words, like ``smog'' instead of ``smokey fog''.  In order for any
language to be useful, it must be extensible.

\section* {Shakey Functions}

In the Shakey language, new words are created by defining {\it
functions}.  The name of the function is associated to its meaning,
and whenever that name is used in the future, the associated meaning
is looked up and executed.  

It is important to understand the difference between a function
definition and a function call.  The code for the function definition
will appear above the {\code main} program.  The function code is read
and digested by the computer, but the code is not executed until the
function is actually invoked or called.  The collection of function
names and their associated definitions is the robots {\it dictionary}
of terms.

\subsection*{Syntax of a Function Call}
How are functions called?  All of the primitive commands are
functions, and they are called by attaching the open and close
parentheses to the function name.  To call the {\code step} function,
we use the program statement {\code step();}.  (The semi-colon at the
end is technically not part of the function call.  It is a symbol used
to signal the end of the statement.)

For example, if you were to define a function named {\code threeStep},
then it would later be called as {\code threeStep()}.

\subsection*{Syntax of a Function Definition}
A function definition begins with the special word {\code function},
followed by the name you have choosen and some parentheses.  The
program statements that define the meaning of the function are
enclosed in curly brackets.

\begin{code}
// Move three steps forward in the current direction.
// THIS IS A FUNCTION DEFINITION
function threeStep() {
  step();
  step();
  step();
}
\end{code}

\section* {All Together Now... A Functional Shakey Program}

Here's a complete program, that will move Shakey in a square dropping
items at each corner.

\begin{code}
// Move three steps forward in the current direction.
function threeStep() {
  step();
  step();
  step();
}

// Drop items in each corner of a 4x4 square.
function main() {
  // upper right hand corner
  right();
  threeStep();  // THIS IS A FUNCTION CALL
  drop();

  // lower right hand corner
  right();
  threeStep();
  drop();

  // lower left hand corner
  right();
  threeStep();
  drop();

  // upper left hand corner
  right();
  threeStep();
  drop();
}
\end{code}

\begin{quest}
Do you notice anything interesting about the main function?
\ans
The main function consists of four identical groups of three
statements.  This redundancy can be easily eliminated by defining and
using another function: {\code oneCorner}.

\begin{code}
// Move three steps forward in the current direction.
function threeStep() {
  step();
  step();
  step();
}

// Turn, walk to the next corner, and drop.
function oneCorner() {
  right();
  threeStep();
  drop();
}

// Drop items in each corner of a 4x4 square.
function main() {
  // upper right hand corner
  oneCorner();

  // lower right hand corner
  oneCorner();

  // lower left hand corner
  oneCorner();

  // upper left hand corner
  oneCorner();
}
\end{code}
\end{quest}

\section* {Functions that call functions are the luckiest functions...}

\begin{quest}
Is it syntactically correct for a user-defined function to call
another user-defined function?
\ans
Yes, absolutely!  Here's a rather simple example:

\begin{code}
function twoStep() {
  step();
  step();
}

function threeStep() {
  step();
  twoStep();
}

function fiveStep() {
  twoStep();
  threeStep();
}
\end{code}
\end{quest}

\section* {Hurdles Revisited}

\begin{quest}
Take the time right now to redo the Hurdles program, making good use
of functions.  Work out your solution on paper.  Then take a look at
the solution provided here.  It may differ radically from your
personal solution.  For your convenience, we repeat the pseudo-code
solution given in the previous module:

\begin{code}
  // Hurdles world loaded.

  //-----------------------
  // JUMP THE FIRST HURDLE.
  //-----------------------
  // Take off...
  // Go up the left side...
  // Round the top and pickup the flag...
  // Go down the right side...
  // Get set for the next jump...

  //------------------------
  // JUMP THE SECOND HURDLE.
  //------------------------
  // same as above...

  //-----------------------
  // JUMP THE THIRD HURDLE.
  //-----------------------
  // same as above...

  //----------------------------------
  // JUMP THE FORTH (AND LAST) HURDLE.
  //----------------------------------
  // same as above...
}
\end{code}
\ans
\anchor{hurdles}{}
\begin{code}
// Pass over the top of the hurdle, picking up the flag.
function roundTop() {
  right();
  step();
  pickup();  // pick up flag on top of hurdle
  step();
  right();
}

// Take three steps, up or down one side of the hurdle.
function threeStep() {
  step();
  step();
  step();
}

// Jump over one hurdle, returning to same relative position
// and orientation in front of the next hurdle.
function jumpOneHurdle() {
  // take off
  right();
  step();
  left();

  threeStep();  // go up the left side
  roundTop();   // over the top
  threeStep();  // and down the right side

  // nail the landing
  left();
  step();
  left();
}

// Jump four hurdles, one after the other, collecting the
// flags at the top of each hurdle.
function main() {
  jumpOneHurdle();
  jumpOneHurdle();
  jumpOneHurdle();
  jumpOneHurdle();
}
\end{code}
\end{quest}

\section* {Why Functions?}

\begin{quest}
As you have seen, one important reason for using functions is to {\it
eliminate redundant code}.  Can you think of another reason?
\ans
Using functions has the added advantage that your program becomes more
{\it readable}, assuming that you give meaningful names to your
functions.  For example, Shakey has just learned a new dance step, and
now he wants to teach you.  See if you can follow along:

\begin{code}
function stepSideways() {
  right();
  step();
  left();
}

function turnYourselfAround() {
  left();
  left();
  left();
  left();
}

function hokeyPokey() {
  left();
  right();
  right();
  left();
}

function thatsWhatItsAllAbout() {
  drop();
  stepSideways();
}

function main() {
  hokeyPokey();
  turnYourselfAround();
  thatsWhatItsAllAbout();
}
\end{code}

This is what the program would look like if we did not use any
functions.  Which version do you find is easier to follow?

\begin{code}
function main() {
  left();
  right();
  right();
  left();
  left();
  left();
  left();
  left();
  drop();
  right();
  step();
  left();
}
\end{code}
\end{quest}

\begin{quest}
OK, that's two good reasons so far for using functions.  Can you think
of any more?
\ans
There are at least two more important reasons for using functions.  

\begin{enumerate}
\item{}
Functions allow for future {\it modifiability} of the program.  If a
program is well-designed, then minor changes in the problem
description should result in minor changes in the problem solution.
After all, who really knows what a hokey-pokey is?

As a more concrete example, suppose the height of a hurdle changes.
Obviously this necessitates some changes in the program solution.
Fortunately, it is relatively easy to locate the area of the code that
requires changing.  Since we isolated the code for each hurdle in a
single function, we need only concentrate on this particular function,
not the entire program.  If we had written our solution using only a
main function, then we would have to hunt for every point that relied
on the height of the hurdle.

If there is a lot of redundant code, then the programmer can easily
overlook one block of code that needs changing.  Such bugs are very
difficult to detect.

\item{}
A programmer can build up a personal {\it library of common functions}
that can be used in many different programs.  These library functions
are new tools that can be used when building future programs.  For
example, you may find that your {\code stepBackwards} function that you
define for one program may also be applicable in another program.  It
would be convenient to just cut and paste its definition into your new
program file.

This avoids having to reinvent the wheel everytime you write a new
program.
\end{enumerate}

\end{quest}

\begin{quest}
At the risk of being redundant, name as many reasons as you can for
using functions in a program.
\ans
\begin{itemize}
\item{}
Functions eliminate redundant code.

\item{}
Functions make a program more readable.

\item{}
Functions aid in modifiability of programs.

\item{}
Functions allow programmers to reuse existing code in new programs.
\end{itemize}

\end{quest}

\begin{quest}
Do you think it is useful to write a function for a subtask if those
instructions are only executed once?
\ans
Yes!  Functions add structure to a program, and the English words and
phrases used to denote a function makes the program more
understandable. 
\end{quest}

\begin{lab*}
\subsection* {Building Shakey Functions}
\begin{exercise}
Bring up the Shakey environment.  There is an additional button at the
top with the label ``New Function''.  Click on this button now.  A
dialog box appears.  Type {\code turnAround} in the text field and
then click on the {\code left} button twice.  You should see Shakey
perform the instructions so that he is now facing south.  If you click
on the ``Create'' button, then these instructions are recorded, and
are available for use in your program by selecting the name {\code
turnAround} from the Dictionary.

Create another new function named {\code stepBackwards} which is
defined as {\code turnAround}, {\code step}, {\code turnAround}.

Practice by implementing the 
\link{hurdles}{Hurdles program} that you developed
earlier.
\end{exercise}

There is one caveat you should be aware of.  If you redefine a
function, {\code turnAround} for example, then you will also need to
redefine any functions that make use of {\code turnAround}.  So, if
after having defined both {\code turnAround} and {\code stepBackwards}
you realize that you have an extra {\code left} in {\code turnAround},
you can go back and re-create the definition of {\code turnAround},
but you'll also have to go back and re-create the definition of {\code
stepBackwards}, even though {\code stepBackwards} is not directly
changed.  This is just an artifact of the way in which the Shakey
applet was written.

\subsection* {Shakey the Farmer}
\begin{exercise}
Shakey the farmer needs to havest some rows of corn.  Load the {\code
Harvest} world and program Shakey to pick up all the ears of corn, row
by row, in a systematic fashion.

\begin{hint}{Getting Started}
To perform this task, Shakey must walk over all the rows to be
harvested.  (Alternatively, he could harvest column by column, but
that is essentially the same solution.)

\begin{quest}
How can Shakey pick a single row?
\ans
Shakey can move west to east across the southernmost unpicked row of
corn, picking each ear as he moves.

\image[center]{icons/hint1.gif} 

\end{quest}

\begin{quest}
How can Shakey pick the entire field?
\ans
Since Shakey is not standing on a corn ear initially, he will have to
move to the first corn ear before starting to harvest the first row.

\image[center]{icons/hint2.gif}

After harvesting one row...

\image[center]{icons/hint3.gif}

... Shakey turns around.

\image[center]{icons/hint4.gif}

He moves back to the western side of the field...

\image[center]{icons/hint5.gif}

...and then moves north one block, faces east, so that he's all ready
to start the next row.

\image[center]{icons/hint6.gif}

He repeats these actions until each row in the field is harvested.

\end{quest}

\begin{quest}
Can you rewrite the solution just described in pseudo-code?
\ans
\begin{code}
// Step onto the first corn ear on the southernmost row.

// Harvest one row of corn.
// Turn around.
// Return to starting position.
// Turn north and take a step.

// Repeat the above four steps for as many additional rows of
//   corn are in the field.
\end{code}
\end{quest}

\begin{quest}
Are there any disadvantages to this solution?
\ans
Yes, each time Shakey returns to his starting position he does so by
walking down the previously picked row of corn.  As he walks, he does
no additional work.  This is not the most {\it efficient} use of
Shakeys energies.  

It would be better if, after harvesting one row, Shakey were to move
north one location and then travel west down the next row of corn,
harvesting as he goes.  In the following picture, Shakey has already
harvested the first row, and now he is working on the second one as he
moves westward.

\image[center]{icons/hint7.gif}

Shakey can then reposition himself to begin the entire process over
for the next {\it two} rows.  Imagine that the rows are numbered 1, 2,
3, and so on, starting from the southern most row and moving
northward.  Then, whenever Shakey is moving east, he is working on an
odd numbered row, and whenever he is moving west, he is working on an
even numbered row.

If Shakey repeats these steps the appropriate number of times, the
entire field will be harvested.  This solution works fine as long as
there are an even number of rows in the field.
\end{quest}

\begin{quest}
Can you rewrite this more efficient solution in pseudo-code?
\ans
\begin{code}
// Step onto the first corn ear on the southernmost row.

// Harvest one row of corn.
// Position Shakey on the last corn ear on (what is now) 
//    the southernmost row, facing west.
// Harvest one row of corn.
// Position Shakey in same relative starting position.

// Repeat the above four steps the appropriate number of times.
\end{code}
\end{quest}

\end{hint}

\end{exercise}

\subsection* {Shakey the Mountain Climber}
\begin{exercise}
Shakey, the mountain climber, is on vacation.  He has decided to scale
the peak in the Mountain world.  Shakey is not Superman.  He must
follow the contours of the mountain closely, going up and then down.
Make good use of functions in your solution.
\end{exercise}

\subsection* {Shakey the Shopper, Part II}
\begin{exercise}
Redo the Shopping exercise from the previous module, making good use
of functions in your solution.
\end{exercise}

\end{lab*}


\section* {Bride of Shakey: Shakette}

\begin{center}
{\font{+2}
{\bf Can we build a better robot?}
}
\end{center}

We conclude this module with an overview of the next important topics
in programming in the context of Shakey.  We will not go into these
concepts in great detail and it is included here only to give you a
perspective of where we are headed.  

Here are some improvements that the next generation of Shakey robots,
the long awaited Shakette series, should support:

\begin{enumerate}
\item{}
The robot should be equipped with sensors of some sort so that she
can detect whether or not she is standing on an item, or whether or
not there is a wall directly in front of her.  We'll call these two
sensors {\code onAnItem} and {\code wallInFront}.  When these sensors
are queried, they respond with either ``true'' or ``false'', depending
on the current conditions.

The programming language that drives this new robot must be able to
access the sensors and make decisions based on the results.  If we
consult the {\code wallInFront} sensor and it tells us that there is
indeed a wall directly in front of the robot, then we certainly do not
want to take a step at this point.  You can imagine being able to
write code of the following form:

\begin{code}
// Try to move forward.
if (wallInFront())
  // Yes! I AM facing a wall... I'd better turn away.
  left();
else
  // Good... the path is clear... I'll just take a step.
  step();

// Try to pick up an object.
if (onAnItem())
  // Wow, I found something! I'll just pick it right up.
  pickup();
else
  // I don't see anything here... it's safe to drop an item.
  drop();
\end{code}

Programming instructions which allow us to test a condition, by using
the robots ``eyes'', and then, depending on the outcome, take one of
two possible actions are called {\it branching instructions}.  The
{\code if-else} statement above is an example of a branching
instruction.

\item{}
We have seen several instances where the robot must repeat one or more
instructions a fixed number of times, for example:

\begin{code}
function main() {
  jumpOneHurdle();
  jumpOneHurdle();
  jumpOneHurdle();
  jumpOneHurdle();
}
\end{code}

What if there were a hundred hurdles?  Then we would need one hundred
function calls.  What if we didn't know exactly how many hurdles there
were in advance.  It would certainly be nice if we could just keep on
jumping as long as there were hurdles to jump.  

\begin{code}
function main() {
  // I'll position myself so that I am facing the first hurdle.
  right();
  step();
  while (wallInFront()) {
    // Oh goodie!  There IS another hurdle to jump!
    // Better reset so that jumpOneHurdle still works.
    stepBackwards();
    left();

    jumpOneHurdle();
    // Whew, that was fun.  

    // Are there anymore hurdles?
    // I'll just get in position so that I can check.
    right();
    step();

    // Hit the end of the statement block...
    // ...that means I must check my while condition and
    // possibly repeat these instructions.
  }

  // No more hurdles... go back to where I should have landed.
  stepBackwards();
  left();
} // All done!
\end{code}

The {\code while} statement above is an example of a {\it looping
instruction}.  This instruction repeats the enclosed sequence of
statements (called the {\it body} of the loop) as long as the
specified condition is true.  That is, as long as there is a wall in
front of the robot at the point in time when the condition is tested,
the body of the loop is executed.  This test is performed when the
statement is first encountered and at the end of each execution of the
loop body.

\item{}
Just what are those open and close parentheses, {\code ()}, for?  They
are glued on to each function call.  Well, it sure would be nice to be
able to have functions that were sent a little information.  For
example, it would be convenient to have a function named {\code
multiStep} that could take any number of steps.  How does she know how
many to take?  The programmer puts the desired number inside the
parentheses.

\begin{code}
multiStep(3);  // take exactly 3 steps
multiStep(15); // take exactly 15 steps
multiStep(0);  // stay put
\end{code}

Now we don't have to litter our code with a zillion little functions
like {\code twoStep}, {\code threeStep}, {\code fourStep}, and so on.

\item{}
It would be nice if our robot could respond to external stimuli as she
was running a program.  For example, we may want her to pause and wait
for us (the user) to input a number to her, and then have her take
that many steps, or some such thing.

It would also be nice if she could take to us as she works, giving up
some status information, such as ``I'm going to pick up an item now''
and ``Ok, I've got it.  Now, let's see if there is a wall in front of
me.''

Programming instructions to control our robots ``ears'' and ``mouth''
are called {\it input/output instructions}.
\end{enumerate}

We will not pursue these ideas by developing the Shakey language any
further.  He has served his purpose and now it is time to move on to a
``real'' programming language.  But these are all powerful tools, and
they exist in all programming languages, in one form or another.  It's
just a matter of learning the particular syntax for the language you
are dealing with.
\end{document}