chapter09.html

think like a computer scientist

<BR><BR>
<H3>9.7 Fill-in functions</H3>

<P>Occasionally you will see functions like <TT>addTime</TT> written with a 
different interface (different arguments and return values). Instead of 
creating a new object every time <TT>addTime</TT> is called, we could require 
the caller to provide an ``empty'' object where <TT>addTime</TT> can store the 
result. Compare the following with the previous version:</P>

<PRE>
void addTimeFill (const Time& t1, const Time& t2, Time& sum) {
  sum.hour = t1.hour + t2.hour;
  sum.minute = t1.minute + t2.minute;
  sum.second = t1.second + t2.second;

  if (sum.second >= 60.0) {
    sum.second -= 60.0;
    sum.minute += 1;
  }
  if (sum.minute >= 60) {
    sum.minute -= 60;
    sum.hour += 1;
  }
}
</PRE>

<P>One advantage of this approach is that the caller has the option of reusing 
the same object repeatedly to perform a series of additions. This can be 
slightly more efficient, although it can be confusing enough to cause subtle 
errors. For the vast majority of programming, it is worth a spending a little 
run time to avoid a lot of debugging time.</P>

<P>Notice that the first two parameters can be declared <TT>const</TT>, but the
third cannot.</P>


<BR><BR>
<H3>9.9 Which is best?</H3>

<P>Anything that can be done with modifiers and fill-in functions can also be 
done with pure functions. In fact, there are programming languages, called 
<B>functional</B> programming languages, that only allow pure functions. Some 
programmers believe that programs that use pure functions are faster to develop
and less error-prone than programs that use modifiers. Nevertheless, there are 
times when modifiers are convenient, and cases where functional programs are 
less efficient.</P>

<P>In general, I recommend that you write pure functions whenever it is 
reasonable to do so, and resort to modifiers only if there is a compelling 
advantage. This approach might be called a functional programming style.</P>


<BR><BR>
<H3>9.9 Incremental development versus planning</H3>

<P>In this chapter I have demonstrated an approach to program development I 
refer to as <B>rapid prototyping with iterative improvement</B>. In each case, 
I wrote a rough draft (or prototype) that performed the basic calculation, and 
then tested it on a few cases, correcting flaws as I found them.</P>

<P>Although this approach can be effective, it can lead to code that is 
unnecessarily complicated---since it deals with many special cases---and 
unreliable---since it is hard to know if you have found all the errors.</P>

<P>An alternative is high-level planning, in which a little insight into the 
problem can make the programming much easier. In this case the insight is that 
a <TT>Time</TT> is really a three-digit number in base 60! The <TT>second</TT> 
is the ``ones column,'' the <TT>minute</TT> is the ``60's column'', and the 
<TT>hour</TT> is the ``3600's column.''</P>

<P>When we wrote <TT>addTime</TT> and <TT>increment</TT>, we were effectively 
doing addition in base 60, which is why we had to ``carry'' from one column to 
the next.</P>

<P>Thus an alternate approach to the whole problem is to convert <TT>Time</TT>s
into <TT>double</TT>s and take advantage of the fact that the computer already 
knows how to do arithmetic with <TT>double</TT>s. Here is a function that 
converts a <TT>Time</TT> into a <TT>double</TT>:</P>

<PRE>
double convertToSeconds (const Time& t) {
  int minutes = t.hour * 60 + t.minute;
  double seconds = minutes * 60 + t.second;
  return seconds;
}
</PRE>

<P>Now all we need is a way to convert from a <TT>double</TT> to a <TT>Time</TT>object:</P>

<PRE>
Time makeTime (double secs) {
  Time time;
  time.hour = int (secs / 3600.0);
  secs -= time.hour * 3600.0;
  time.minute = int (secs / 60.0);
  secs -= time.minute * 60;
  time.second = secs;
  return time;
}
</PRE>

<P>You might have to think a bit to convince yourself that the technique I am 
using to convert from one base to another is correct. Assuming you are 
convinced, we can use these functions to rewrite <TT>addTime</TT>:</P>

<PRE>
Time addTime (const Time& t1, const Time& t2) {
  double seconds = convertToSeconds (t1) + convertToSeconds (t2);
  return makeTime (seconds);
}
</PRE>

<P>This is much shorter than the original version, and it is much easier to 
demonstrate that it is correct (assuming, as usual, that the functions it calls
are correct). As an exercise, rewrite <TT>increment</TT> the same way.</P>


<BR><BR>
<H3>9.10 Generalization</H3>

<P>In some ways converting from base 60 to base 10 and back is harder than 
just dealing with times. Base conversion is more abstract; our intuition for 
dealing with times is better.</P>

<P>But if we have the insight to treat times as base 60 numbers, and make the 
investment of writing the conversion functions (<TT>convertToSeconds</TT> and 
<TT>makeTime</TT>), we get a program that is shorter, easier to read and debug,
and more reliable.</P>

<P>It is also easier to add more features later. For example, imagine 
subtracting two <TT>Time</TT>s to find the duration between them. The naive 
approach would be to implement subtraction with borrowing. Using the conversion
functions would be easier and more likely to be correct.</P>

<P>Ironically, sometimes making a problem harder (more general) makes is easier
(fewer special cases, fewer opportunities for error).</P>


<BR><BR>
<H3>9.11 Algorithms</H3>

<P>When you write a general solution for a class of problems, as opposed to a 
specific solution to a single problem, you have written an <B>algorithm</B>. I 
mentioned this word in Chapter 1, but did not define it carefully. It is not 
easy to define, so I will try a couple of approaches.</P>

<P>First, consider something that is not an algorithm. When you learned to 
multiply single-digit numbers, you probably memorized the multiplication table.
In effect, you memorized 100 specific solutions. That kind of knowledge is not 
really algorithmic.</P>

<P>But if you were ``lazy,'' you probably cheated by learning a few tricks. For
example, to find the product of <TT>n</TT> and 9, you can write <TT>n-1</TT> as
the first digit and <TT>10-n</TT> as the second digit. This trick is a general 
solution for multiplying any single-digit number by 9. That's an algorithm!</P>

<P>Similarly, the techniques you learned for addition with carrying, 
subtraction with borrowing, and long division are all algorithms. One of the 
characteristics of algorithms is that they do not require any intelligence to 
carry out. They are mechanical processes in which each step follows from the 
last according to a simple set of rules.</P>

<P>In my opinion, it is embarrassing that humans spend so much time in school 
learning to execute algorithms that, quite literally, require no 
intelligence.</P>

<P>On the other hand, the process of designing algorithms is interesting, 
intellectually challenging, and a central part of what we call programming.</P>

<P>Some of the things that people do naturally, without difficulty or 
conscious thought, are the most difficult to express algorithmically. 
Understanding natural language is a good example. We all do it, but so far no 
one has been able to explain <I>how</I> we do it, at least not in the form of 
an algorithm.</P>

<P>Later in this book, you will have the opportunity to design simple 
algorithms for a variety of problems. If you take the next class in the 
Computer Science sequence, Data Structures, you will see some of the most 
interesting, clever, and useful algorithms computer science has produced.</P>


<BR><BR>
<H3>9.12 Glossary</H3>

<DL>
  <DT>instance:</DT><DD> An example from a category. My cat is an instance of 
  the category ``feline things.'' Every object is an instance of some type.</DD>

  <DT>instance variable:</DT><DD> One of the named data items that make up an 
  structure. Each structure has its own copy of the instance variables for its 
  type.</DD>

  <DT>constant reference parameter:</DT><DD> A parameter that is passed by 
  reference but that cannot be modified.</DD>

  <DT>pure function:</DT><DD> A function whose result depends only on its 
  parameters, and that has so effects other than returning a value.</DD>

  <DT>functional programming style:</DT><DD> A style of program design in 
  which the majority of functions are pure.</DD>

  <DT>modifier:</DT><DD> A function that changes one or more of the objects it 
  receives as parameters, and usually returns <TT>void</TT>.</DD>

  <DT>fill-in function:</DT><DD> A function that takes an ``empty'' object as a
  parameter and fills it its instance variables instead of generating a return 
  value.</DD>

  <DT>algorithm:</DT><DD> A set of instructions for solving a class of problems
  by a mechanical, unintelligent process.</DD>
</DL>

<BR>
<DIV CLASS=navigation><HR>
  <TABLE ALIGN=center WIDTH="100%" CELLPADDING=0 CELLSPACING=2>
  <TR>
    <TD><A HREF="chapter10.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter10.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="next" 
      SRC="images/next.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/next.gif"></A>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="up" 
      SRC="images/up.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/up.gif"></A>
    </TD>

    <TD><A HREF="chapter08.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter08.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="previous"
      SRC="images/previous.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/previous.gif"></A>
    </TD>

    <TD ALIGN=center BGCOLOR="#99CCFF" WIDTH="100%">
      <B CLASS=title>How to Think Like a Computer Scientist: Chapter 9</B>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="contents"
      SRC="images/contents.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/contents.gif"></A>
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>
  </TR>
  </TABLE>

  <B CLASS=navlabel>Next:</B>
  <SPAN CLASS=sectref><A HREF="chapter10.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter10.html">Chapter 10</A></SPAN>

  <B CLASS=navlabel>Up:</B>
  <SPAN CLASS=sectref><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">Index</A></SPAN>

  <B CLASS=navlabel>Previous:</B>
  <SPAN CLASS=sectref><A HREF="chapter08.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter08.html">Chapter 8</A></SPAN>

  <HR>
</DIV>
</BODY>
</HTML>