To be presented at the Northeastern Small College Computing Conference, April 18-20, 1996.
Rick Mercer
A. Michael Berman
Abstract: Many colleges are integrating object-oriented (OO) technology and/or C++ into the first year of the computing curriculum. The path towards this goal can be difficult, but it can also be rewarding and of great benefit to students. This paper shares the experiences of two instructors, at different colleges, who are making this transition. It discusses C++ as the first and only language in CS1 and CS2 along with some OO concepts that have proved to be an effective part of the first year. We are not trying to persuade anyone to adopt OO technology and/or C++. Instead, we offer ten suggestions for those in the process of, or thinking about, using the OO/C++ approach. Some suggestions are very general, others are quite specific.
Much of the writing on OO emphasizes its revolutionary nature-the world becomes objects, and nothing's the same again. Unfortunately, viewing OO as a radical new way of thinking about software induces paralysis in many computer science instructors and departments. They think that without throwing everything out and starting over, they cannot achieve true OO nirvana, and that unless they are OO purists, their students will remain in the Dark Ages. For most of us, the natural response is to deny the whole thing, call it a fad, and stick with what we know and love.
There may be an OO revolution, but that does not mean you have to make the change all at once. Instead, you can incorporate what you know worked before, and bring in the best that OO has to offer, a little at a time as you understand it. We all know that what we teach now in the first year is quite different from what we taught 10 years ago, and we assume that we'll be doing something else 10 years from now, but there are still central issues that have not changed and that we believe will carry on. Students will still struggle with issues like control flow, distinguishing between the name of an object and its value, data flow within a program, and understanding a specification and converting it to code. We've found that, in some cases, OO makes these things easier to teach, not harder. We've also found that as our understanding of OO concepts deepens we find new ways and new approaches, and our courses get "more Object-Oriented." We don't believe that it's a binary proposition. Don't worry about the purists-worry about your students and what you have to teach them, and you will succeed.
For most purposes, the terms class and data type are interchangeable. The terms variable and object are also interchangeable [Booch 91]. There is nothing wrong with the continued use of variable and data type; however, talking about classes and objects early has a payoff-especially if used immediately and fairly often. Students have indicated no difficulty using double and string objects within their programs. Students also have no trouble referring to string and double as classes.
We can keep the usual definitions for variable and data type to describe object and class, respectively. An object has three characteristics: name, value, and operations [Booch 91]. A class describes the kinds of values (data) an object may store along with the operations that manipulate those values. With these familiar definitions, students understand that the following C++ code
double x = 0.0;
initializes the state of a double object named x to 0.0. Students also readily understand the operations that may be applied to x-assignment, input/output, *, +, -, /, sqrt, ++, and so on. Adopting this new terminology pays off when we begin to talk about list, table, BankAccount, Employee, button, and window objects. Saying "window object" is easier than saying "window variable".
This section is aimed at those thinking of switching from some language X, to C as a first language. It also is meant to assuage those who feel that C should not be used as the first language (the authors of this paper are among this group).
Bjarne Stroustrup-the C++ design leader-describes C++ as a better C. C++ provides better support for procedural and modular programming. As a superset of C, C++ also provides support for data abstraction and object-oriented programming [Stroustrup 92]. C++ is also a safer C. The first examples of a better and safer C are the standard input and output objects known as cin and cout, respectively. Using cin and cout, rather than printf and scanf, is more intuitive, does not require understanding pointers, and is less likely to crash the system. Using these two input/output objects in CS1/CS2 is now widely accepted.
A string class is another example of a better and safer C. With C++, we can use, buy, or implement a string class that performs behind-the-scenes memory allocation and deallocation to avoid system crashes and memory leaks. We need not subject our students to char* objects or arrays of chars just to store someone's first name. Early in the first course, students become accustomed to string objects as a natural part of the language. String classes are readily available with many compilers or by way of the internet. Consider using the C++ string class specification of the draft standard document. [Koenig string]-or at least a subset of it.
The primitive C array construct-pointers in disguise-also causes problems for C programmers. C++ now has a proposed standard specification for a vector class that is similar to C arrays. In contrast to the onerous C arrays (pointers), the implementor may provide a safe vector class with subscript range checking. Some vendors already provide subscript range-checking as an option.
The declaration of three vector objects is shown next. The class passed to vector-double, string, and BankAccount-specifies the class of objects that may be stored in the vector (vector is a generic container class).
vector<double> test(50); // store up to 500 double objects vector<string> name(100); // store up to 100 string objects vector<BankAccount> account(1000); // store 1,000 BankAccount objects
Even through a vector declaration is different from C arrays, individual elements of a vector object are still referenced in the usual manner through subscripts, preferably with the option of informing the programmer when a subscript is out-of-range.
for(int j = 0; j < 50; j++)
test[j] = -1;
account[0] = BankAccount("Hall", "1234", 100.00);
name[0] = "First string in the vector name";
name[100] = "Run time error if you want"; // Error on some vector implementations
So besides using cin, cout, and safe string objects, consider implementing your own vector class with subscript range checking according to the proposed C++ standard language definition [Koenig vector].
Some people believe OO programming must use inheritance with the accompanying virtual functions and polymorphism. However, there certainly is a place for classes without inheritance [Stroustrup 95]. Lectures on classifications of insects and vehicles can obfuscate rather than elucidate. On the other hand, classes with no apparent inheritance-such as Date or BankAccount-are readily grasped by students. We don't need inheritance early to be OO (even genericity through the C++ template mechanism may be more appropriate than inheritance in the first year). Classes that stand by themselves provide us with a major feature of object-oriented technology-encapsulation -the combination of data and associated operations.
Repeated experience has shown students easily use BankAccount objects, for example. Students were quite capable of listing the behavior and attributes-the operations and data-of a BankAccount class. They have repeatedly done a decent job of providing an initial design. In the next example, data members such as myNumber, myBalance, and so on, [Astrachan 96] store the state of an object. The operations that manipulate the data have the names withdraw, deposit, and balance. With a class declaration like this:
class BankAccount {
public:
BankAccount(string initName, string initNumber, double initBalance);
void withdraw(double amount);
void deposit(double amount);
double balance();
private:
string myName;
string myNumber;
double myBalance;
};
There is perhaps only a subtle difference between this C++ class and a Pascalish approach that has a BankAccount record passed amongst many separate procedures and functions. However, encapsulation provides a major improvement, even without inheritance and polymorphism. Students have shown the ability to understand interfaces such as class BankAccount above and to understand what happens with messages-function calls-like this:
BankAccount anAcct("Hall", "1234", 25.00);
anAcct.deposit(42.50);
anAcct.withdraw(30.00);
cout << anAcct.balance();
Students also accept encapsulation of operations together with the data as a natural formula for implementing data types. And making some classes generic-especially containers classes such as list, stack, queue, for example-allows our encapsulation to work on any type collection of objects.
So if you choose to cover one of the major features of the object-oriented technology-encapsulation, inheritance, or polymorphism-consider starting with encapsulation. You can redesign BankAccount objects in a hierarchy later on if you truly find it necessary. Emphasizing encapsulation early also lays the groundwork for discussing important software engineering issues such as information hiding and data integrity. Also consider genericity as a more important and appropriate first year topic than inheritance.
We have found a slight change of focus prepares students for reuse. Instead of learning to design for reuse-a difficult task even for professionals-students can first learn to reuse. Suggest that we are clients of existing software and that there is a plethora of existing classes to choose from. Also, don't take the standard C++ classes for granted. For example, double objects have very sophisticated implementations. But this "primitive" class elevates to "reusable" when placed in the context of reuse. Other objects that may be used quite often-and very early-include input and output streams (cin and cout), strings, and ints. The GUI framework that comes with some compilers also provides a rich source of reusable objects.
We recommend the avoidance of class overload by limiting the number of instructor-supplied classes. You only need a small number of interesting classes that can first be put to use and then perhaps modified. This prepares students for design and implementation of their classes (especially when students are first required to understand class declarations and function prototypes). There are many classes in the C++ language definition, so avoid using too many non-standard classes, particularly if they will never be used again. Students have much to remember as it is.
Some instructors are under the impression that algorithms disappear once we get into true OO programming. But even though C and C++ have long provided algorithms such as qsort and lsearch, how often have they been used in CS1/CS2? Although the standard template library (stl) ill be delivered with more than 100 algorithms including searching and sorting, we still can and must continue to teach problem-solving. Many computer science instructors reveal sorting for the inherit problem-solving techniques and as a source for the analysis of algorithms. These examples do not disappear. We can still use these examples, but with the OO/C++ model, we have the choice to make the sorting algorithms be part of a class.
Computing Curricula 91 suggests fundamental problem-solving lectures should include: Procedural abstraction, Control structures (selection, iteration, recursion), Data types, and Software design process [ACMIEEE 95]. None of these topics need disappear from the first year, nor should they. Students should still understand fundamental problem-solving, the software design process, and the algorithms that live on the dark (implementation) side of classes. Retain problem-solving.
For example, sequence-the most underrated control structure-may still be a struggle for some novice programmers. Placing the proper steps into the proper order transcends programming languages. This falls into the realm of algorithm development. With C++ we still sequence and use familiar control structures such as if, if...else, for, while, do...while, and recursion. In fact, with C++, control structures can be simplified by using multiple returns such as the following elegant sequential search function [Roberts 95] that is enhanced to search for an object of any class where == is defined:
template <class Type>
int index(Type searchItem, vector<Type> x, int n)
{
//
// pre: The vector x is defined from subscripts 0 through n-1.
// post: Return the position of searchItem in x or
// return -1 if searchItem is not found in x.
//
for(int j = 0; j < n; j++) {
if(searchItem == x[j])
return j; // return the position of searchItem in x
}
return -1; // signal that searchItem was not in x
}
With C++, we avoid awkward Pascalish end of file loops by using the extraction operation itself as the loop test:
while(cin >> x) // process x
With C++, we may also use the break statement to simplify sentinel loops:
while(1)
{
cin >> x;
if(x == sentinel)
break;
// process x
}
The Abstract Data Type is a central theme in most versions of the CS2 course. One of the real frustrations of teaching ADT's in Pascal is that the language provides no method of creating them that's both clean and standard (although the Turbo Pascal Unit comes close). For example, the classic Stack ADT can be easily defined as a C++ class with a definition like this:
template <class StackElementType>
class Stack {
public:
Stack();
void push(StackElementType item);
StackElementType pop();
StackElementType top();
bool isEmpty();
private:
// implementation details
};
Look at all the advantages over the Pascal version-this Stack is generic, it's encapsulated, but it's still the Stack we know and love. You don't have to present an imitation Smalltalk class library with a hundred container types, unless you want to-there are many benefits from simply using classes to implement basic ADT's.
Everybody knows that C++ is a large programming language. The C language legacy contributed many of the pitfalls of C++. However, it's also a language of great richness and power. If you decide to introduce C++ at the introductory level, it will be a lot easier if you, the instructor, know enough about the language to guide your students through it and help them use the language features and idioms that lead to good code that's easy to understand and debug. The information and good taste in Scott Meyers's Effective C++ [Meyers 92] can be quite helpful. Stroustroup's classic The C++ Programming Language [Stroustrup 92], while impenetrable for the typical first-year student, has a lot of insight to offer the instructor, as does his more recent The Design of the C++ Language [Stroustrup 94].
Here's an example. Suppose you teach your students to instantiate
a stack of ints like this: Stack<int>. At some
point later on, a student will want to declare a stack of int
vectors, and they'll write: Stack<vector<int>>.
Unfortunately, this doesn't work, because the sequence ">>"
is treated as a token ">>", so the
code won't compile. Instead, start them out writing "Stack<
int >" with spaces, so that when they write "Stack<
vector<int> >" it will work. To avoid the
problems later, you can prepare the students by showing your template
declarations with the extra spaces. Knowing about some of the
pitfalls of C++ will make it possible for you to steer your students
around them.
If you have a rich library of standard components with which to construct your programs-still more of a goal than a reality for many environments-it might seem that you'd never need to learn about how to create them. We don't agree with this point of view. Sure, for some kinds of programs and programmers, just knowing how to plug pieces together is enough, but we don't see the day coming soon when computer science students won't need to be able to understand sorts or explain what a stack is and how it's implemented.
Some of the concepts that we can learn about when discussing a stack are the relative advantages of contiguous versus pointer-based implementation, and how a stack is used in implementing recursion. Trees provide a virtual laboratory for discussing performance tradeoffs. And while a handy library may provide every kind of linked list we might ever want, where better to learn about pointers?
On the other hand, students do have to understand the advantages of reuse. Certainly, we're coming to end of the days when programmers built every last data structure "from scratch". We believe that reuse will continue to grow as an important theme in the education of the modern software engineer. But that doesn't imply we can completely dispense with learning about data structures. After all, just because few of our students write their own compilers or operating systems, that doesn't mean we've given up teaching about them.
Having the ability to create classes and construct hierarchies through inheritance can help you think about traditional first-year problems in new ways. Take, for example, trees. It's a valuable exercise to abstract the common elements of the various kinds of trees and examine how they might be organized in an inheritance hierarchy. Even the familiar Binary Tree can be developed in new directions, as discussed in "Thinking About Binary Trees in an Object-Oriented World" by Berman and Duvall [Berman & Duvall 96].
As another example, consider an abstract Stack class that defines the usual pop, push, top, and isEmpty interface using pure virtual functions. The abstract class defines the interface, but not the implementation(s). Students may derive classes such as StackAsVector and StackAsList and then implement the "standardized" interface of the abstract class using separate contiguous and pointer based implementations, respectively. This example [Astrachan 95] is a familiar CS2 problem done in a new way. Inheritance provides a framework that requires students to implement the same ADT in different ways.
Objects also allow for more interesting and less trivial programming projects. By providing a few classes, we can teach basic control structures in a new way. For example, one ATM and one bank object are all that's needed for a program that simulates banking operations with an ATM interface [Mercer 95]. It is something most high school students haven't done-at least not yet anyway. Instead of arrays of records near the end of CS1, students now deal with arrays of objects and classes with array data members. Another example of interesting project were made possible with a simplified set of GUI and graphics objects in the Fall of 1995 at Penn State Berks [Epp 95]. Not only did students learn basic control structures with interesting objects, they also experienced some windows programming with the results of program execution coming back at them as a modern interface.
There are many obstacles to overcome during the transition to object technology and C++ in the first year. Sometimes the obstacles are placed there by well-meaning individuals-ourselves. We suggest you make a transition with evolutionary rather than revolutionary execution. Start by defining the three characteristics of an object: name, value, operations. Don't worry about the aHa experiences and hierarchies of classes at first. Instead first consider the goals of your first year and find out if any object technology will help you achieve those goals. For example, we have suggested that CS1 can be made less frustrating with "safe" input, output, string, and vector classes. In CS2, the C++ class is an excellent construct for implementing data types. In summary, we are suggesting you do less than everything, especially at first.
[ACM/IEEE 91] Alan Tucker, et. al. Computing Curricula 1991. Report of the ACM/IEEE-CS Joint Curriculum Task Force, ACM Press, IEEE Computer Society Press, 1991
[Astrachan 95] Owen Astrachan. NSF Sponsored OO Workshop at Colgate University, June 1995.
[Astrachan 96] Owen Astrachan. Teaching Tip from Teaching C++ as an Introductory Language (an electronic Newsletter) Vol::1No 1::1, Feb. 1, 1996, Turing Tarpit Software, pattis@acm.org
[Berman & Duvall 96] Michael Berman and Robert Duvall, Thinking About Binary Trees in an Object-Oriented World, Proceedings of the ACM Technical Symposium on Computer Science Education, 1996.
[Booch 91] Grady Booch, Object-Oriented Design with Applications, Addison Wesley, 1991
[Epp 95] Edd C. Epp. Laboratories for Writing Object-Oriented Graphical User Interfaces Using C++, Manuscript version, Franklin, Beedle and Associates, 1995
[Koenig string] Andrew Koenig. Working Paper for Draft Proposed International Standard for Information Systems-Programming Language C++. Doc No:X3J16/95-0087, April 1995 http://www.cygnus.com/misc/wp/draft/lib-strings.html
[Koenig vector] Andrew Koenig. Working Paper for Draft Proposed International Standard for Information Systems-Programming Language C++. Doc No:X3J16/95-0087, April 1995 http://www.cygnus.com/misc/wp/draft/libcontainers.html
[Mercer 95] Rick Mercer. Computing Fundamentals with C++, Using, Modifying, and Implementing Object Classes. Franklin, Beedle, and Associates. 1995.
[Meyers 92] Scott Meyers. Effective C++: 50 Specific Ways to Improve Your Programs and Designs. Addison-Wesley, 1992.
[Roberts 95] Eric S. Roberts. Loop Exits and Structured Programming: Reopening the Debate, The Papers of the Twenty-Sixth SIGCSE Technical Symposium on Computer Science Education, 1995, pp 268 - 272.
[Stroustrup 92] Bjarne Stroustrup. The C++ Programming Language, Second Edition. Addison-Wesley, 1992.
[Stroustrup 94] Bjarne Stroustrup. The Design and Evolution of C++, Addison-Wesley, 1994.
[Stroustrup 95] Bjarne Stroustrup. C++ is more than an Object-Oriented Language. OOPSLA 1995, Austin Texas.