Teaching Programming With Minimal Examples

D. Hoffman
Department of Computer Science, University of Victoria

P. Walsh
Computing Science Department, Malaspina University-College


ABSTRACT

This paper describes a proven and language-independent technique for teaching computer programming. The technique employs typical-use examples and minimal examples to illustrate language features and programming concepts. Both types of examples are presented to students in the class-room and are made available on-line.

A typical-use example is a simplified version of a real application. It may be short, but is rarely short enough to be presented in its entirety. A minimal example is focused on a single feature or programming concept. It is a complete executable program, crafted to be as short as possible. Minimal examples rarely compute useful results, because so much is left out. However, minimal examples can illustrate key language features with impressive brevity and clarity, because everything not directly relevant is left out.

Keywords: Programming, C++, Perl, Make


1. Introduction

We present a technique for teaching programming by example. Our approach is novel in so far as we make heavy use of minimal examples as well as the more traditional typical-use examples.

A typical-use example is a simplified version of a real application. It is short, but usually not short enough to be presented in its entirety in the class-room. A minimal example is focused on a single feature or programming concept. It is a complete executable program, crafted to be as short as possible. It is instrumented for observability with no attempt to do anything other than to illustrate a point.

Minimal examples advantage both student and teacher. For the student, they facilitate self-study. Students can quickly read, modify, and observe programs and program behaviour. Minimal examples can also be used by students to focus their questions to the instructor and for problem isolation during debugging.

For the instructor, minimal examples are ideal for class presentation as they often fit on a single transparency. Once the examples have been prepared, they can be easily modified for use in exams. A question based on a minimal example usually takes the form: given a program, provide the exact output. These questions are revealing since there is no way to determine the correct output without a thorough understanding of the source code. The answers are easy to grade as they are short and there is only one correct answer.

Our first goal in presenting this work is to demonstrate the use of minimal examples in teaching programming. Our second goal is to promote a certain kind of paper for contributions to WCCCE in the future. Often new teaching proposals, even very good ones, require a substantial change in our current approach. Most of us attending WCCCE are so busy that we cannot find time for such change, and so we often neglect promising teaching proposals because we lack the time to implement them. However, many instructors know of simple, "standalone" techniques that can be thoroughly explained in 20 minutes and can be put into practice with only a small change in our current approach. Like the "little language" approach popularized by languages like Awk, these "little papers" can offer surprisingly good results for modest effort. We hope that this little paper will be followed by others like it at future WCCCE meetings.

2. Minimal Examples in C++

As every C++ [Stroustrup93] programmer and instructor knows, C++ is a complex language. It has many features, and the interactions between those features are often subtle and counterintuitive. Even experienced C++ programmers frequently have misunderstandings about the semantics of features they use regularly.

We have applied minimal examples with excellent results to learning and teaching C++. Our standard approach to a tricky C++ feature is to develop a small set of minimal examples that answer the most important questions about the feature. Usually, the shorter the example, the quicker we can learn from it and the more confidence we have in the answers it yields. As instructors, developing the examples nearly always exposes misunderstandings we have about the feature.

In the remainder of this section, we present minimal examples illustrating (1) constructors and destructors, (2) exceptions, and (3) assignment versus initialization. We have written dozens of other minimal examples illustrating templates, inheritance, virtual functions, and other C++ features.

Throughout the paper, each minimal example is presented in the same format:

Constructors and destructors

Driving question

When are constructors and destructors called for objects that are (i) static, (ii) automatic, and (iii) dynamic?

Program

#include <iostream.h>

class C {
public:  C(int i0) : i(i0) { cout << "C: " << i << endl; }
         ~C() { cout << "~C: " << i << endl; }
private: int i;
};

C c1(1); // static

int main()
{
	cout << "main start" << endl;
	C c2(2); // automatic
	cout << "main middle" << endl;
	C* C3 = new C(3); // dynamic
	cout << "main end" << endl;
}

Output

C: 1
main start
C: 2
main middle
C: 3
main end
~C: 2
~C: 1

Discussion

Every C++ programmer knows something about constructors and destructors. Most programmers, however, do not know precisely when the constructor and destructor are called. It turns out that the timing depends on the storage type of the object. The heart of this example is the class C, designed to be as simple as possible while making construction and destruction visible. Thus, C consists of a constructor and destructor that do nothing but print a message when invoked, and a single member variable used to uniquely identify each C instance. We say that C is "instrumented for observability" and use such instrumentation frequently. With C declared, all that we need do is instantiate C once for each of the three storage types: C's instrumentation takes care of the rest. As the output shows:
  1. a static object is constructed before main is called, and is destroyed after main returns,

  2. an automatic object is constructed at the point at which it is defined, and is destroyed when control leaves the containing block, and

  3. a dynamic object is constructed when the call to new is issued and is never destroyed unless an explicit call to new is made. Misunderstanding about this point is a common cause of memory leaks.
Point 1 has a surprising consequence. Because the constructor for a static object can contain arbitrary C++ code, a C++ program can do a lot of computation, and even abort, without ever invoking main. Many programmers have refused to believe this claim until we show them the above example; all were convinced by the example.

Exceptions

Driving question

What impact do try, throw, and catch have on the flow of control?

Program

#include <iostream.h>

class X {};

void f() {
	cout << "before throw" << endl;
	throw X();
	cout << "after throw" << endl;
}

int main()
{
	cout << "main start" << endl;
	try {
		cout << "before call to f" << endl;
		f();
		cout << "after call to f" << endl;
	}
	catch (X) {
		cout << "X caught" << endl;
	}
	cout << "main end" << endl;
}

Output

main start
before call to f
before throw
X caught
main end

Discussion

C++ exceptions are a powerful feature for handling abnormal situations in complex systems. Perhaps because there is no analogous feature in C, many C++ programmers avoid exceptions entirely, or use them with a dangerously flawed interpretation. This example illustrates the central feature of exceptions: throw is a special kind of unconditional branch. The two "after messages" are never displayed. The function f does not return with an "error return code" (as it would in C); it simply does not return at all. We have found that C programmers find this last point hard to grasp even after a 45-minute lecture; the longer we lecture, the less seems to be understood. This austere example makes the point unmistakably in 10 minutes of study; it speaks more clearly than we do.

Assignment versus initialization

Driving question

What is the difference between assignment and initialization?

Program

#include <iostream.h>

class C {
public:
	C(int i0) : i(i0)
		{ cout << "C(int) i: " << i << endl; }

	C(C& c0) : i(c0.i)
		{ cout << "C(C&) i: " << i << endl; }

	void operator=(C& rhs)
		{ cout << "operator=(C&) lhs: " << i << " rhs: " << rhs.i << endl; }
private:
	int i;
};

int main()
{
	C c0(0);  // initialization
	C c1 = 1  // initialization
	C c2 = c1 // initialization
	c0 = c1;  // assignment
}

Output

C(int) i: 0
C(int) i: 1
C(C&) i: 1
operator=(C&) lhs: 0 rhs: 1

Discussion

As Stroustrup points out
It cannot be overemphasized that assignment and initialization are different operations. [Stroustrup93,page 239]
However, because the "=" symbol may appear in both assignment and initialization, even experienced C++ programmers sometimes confuse the two. This example is based on the class C, instrumented for observability. Here it is the constructors and the operator= function that are instrumented. (With its void return type, this operator= is unconventional but is sufficient for our purposes.) In main are four simple statements showing that the distinguishing characteristic of initialization and assignment is not the "=" symbol. Rather, the crucial issue is whether the object is being created for the first time (initialization), or already existed and is being overwritten (assignment).

3. Minimal Examples in Perl

Perl [Wall91] is a public-domain language developed by Larry Wall, and has been ported to the Unix, DOS, and Macintosh platforms. Perl is a blend of the Unix shell languages, and the Unix awk, sed, and grep utilities. It is widely used by programmers, systems administrators and database administrators.

Multi-dimensional Arrays

Driving Question

An array in Perl is a sequence of scalars. How are arrays of composites (multi-dimensional arrays) emulated?

Program

$;=A;
$x{1,1}=a;
$x{1,2}=b;
$x{2,1}=c;
foreach $key (keys(%x)) {
   print "x{$key} = ",$x{$key},"\n";
}

Output

x{1A1} = a
x{2A1} = c
x{1A2} = b

Discussion

Perl emulates multi-dimensional arrays using associative arrays. An associative array in Perl consists of zero or more key/value pairs. Each key and each value must be a scalar: a string or a number. A multi-dimensional reference is joined into a string that is then used in the normal way to index an associative array. For example, x{1,1} is translated by Perl into x{join($;,1,1)}. The effect of this is to join the strings "1" and "1" together into a single string. The join function uses the value of the special variable $; as a separator. Above, we assigned $; the value "A" (the value of $; defaults to null). Consequently, the join-produced string is "1A1" and the the value of x{1,1} is the scalar associated with the string "1A1".

Perl metacharacters

Driving Question

What strings are matched by the Perl metacharacters +, *, ^ and []?

Program

@a = ('bb',           'bb*',    
      ' *',           ' +',
      '^b',           '[^b]*',   
);

$s0 = "aa*bbb+1234?";

foreach $s (@a) {
    if ($s0 =~ /$s/) {
        print "$s: $`!$&!$'\n";
    } else {
        print "no match\n";
    }
}

Output

bb: aa*!bb!b+1234?
bb*: aa*!bbb!+1234?
 *: !!aa*bbb+1234?
no match
no match
[^b]*: !aa*!bbb+1234?

Discussion

The string $s0 is matched against all the patterns in @a. For each pattern, the pattern and the value of $s0 are written out on a single line . In the output, $s0 is partitioned such that the substring matched by the pattern is enclosed by a pair of exclamation marks ('!'). Note the distinction between "no match" and a match on the empty string.

The meanings of the six patterns in @a are as follows:

4. Minimal Examples in Make

Make is a Unix tool that streamlines the process of generating and maintaining object files and executable programs. Make allows the programmer to compile programs consistently and eliminates unnecessary recompilation of modules that are unaffected by source code changes. Make reads a user-created program that contains information on what files to build and how to build them. Make programs take the form:

target...: [dependency ... ]
	[rule]
	...

Make will build a target if one or more of its prerequisite files have been modified since the target was last built. A target is built by executing its associated rule. File time-stamps are used to determine if a prerequisite file is older than its target.

Make dependency scan

Driving question

In what order are targets processed by make?

Program

a: b c
        touch a
c:
        touch c
b:
        touch b

Output

touch b
touch c
touch a

Discussion

Once make begins, it processes targets as it encounters them in a depth-first dependency scan. In the above example, let us assume that the files a, b and c do not exist in the current directory. Make starts with target a. Target a has dependencies b and c. They have not been checked yet. Consequently, make defers processing a until b and c have been checked against any dependencies they might have. Next, b is checked. It has no dependencies so make considers it out of date and builds it by executing its associated rule. Next, c is checked. It has no dependencies so make considers it out of date and builds it by executing its associated rule. Finally, the way is clear to process a. Since at least one of a's dependencies have been modified, a is considered out of date and must be built by executing its associated rule.

5. Conclusions

We have presented minimal examples in C++, Perl, and Make, showing how just a dozen or so carefully chosen lines can yield impressive clarity. With minimal examples, the guiding principle is "more is less". We trim the examples brutally, asking the same question about every keystroke: "Can it be omitted?".

We routinely "instrument" the examples, using print statements to make selected aspects of program behavior visible. Frequently, an example is little more than a few uses of a language feature, plus the appropriate instrumentation.

While this paper emphasizes minimal examples, it is important to note that they are most effective in combination with typical-use examples. In this paper, we have emphasized minimal examples because most readers are already familiar with typical-use examples.

We have used minimal examples successfully in first, second, third, and fourth year courses, and in industrial short courses. Across programming languages and skill levels, we have found minimal examples to be an effective technique: enjoyable to create and present, and revealing and easy to grade on exams.


References

Stroustrup93
Bjarne Stroustrup, "The C++ Programming Language", Addison-Wesley, 1993.
Wall91
Larry Wall and Randal L. Schwartz, "Programming Perl", O'Reilly and Associates, 1991.