AP Computer Science: Object Oriented Programming

A Bit of History

I grew up with computers from the late 60's to the present day. Now my next generation (my son) is trying his hand at learning the art. But what should he learn? Do I take him through an entire history of the growing pains of computers where memory was scarce and expensive. Where our programming languages had little in the way of libraries to do useful things? I don't think so. He doesn't need a complete review of the past to come up to speed with the way things are done today. I had to live rewritting my libraries from scratch each time I switched jobs or changed platforms. He doesn't. The field is different today and the popular languages have large libraries associated with them. He and his fellow Comp Sci students should be able to benefit from efforts of previous computer scientists.

When I first started out with computers the BASIC programming language was avaialble on most machines in use at that time. BASIC had FOR loops and IF statements but it also had a GOTO statement. A BASIC program would have line numbers and you would tell the computer to GOTO a certain line number. Programs were littered with GOTOs. Then I got to College and it was proclaimed that GOTOs were taboo. We now had "Structured" programming languages (like PASCAL, ALGOL, PL/1) and a well written program would not even need to use GOTOs. Edgar Dykstra a giant in computer science wrote the classic treatise in a letter to the programming journal "Communications of the ACM" (see reference 1). This was the beginning of the "Structured" programming paradigm, which can be summed up with the title to a book by Niklaus Wirth: Algorithms + Data Structures = Programs.

From GOTO to Object Oriented

Now we have Object Oriented programming languages and a similar paper appeared in communications of the ACM by Ralph Westfall (see reference 2). Declaring that we teach Object Oriented Programming wrong from the very beginning. The quintessential first program in Computer Science is the "Hello World" program. Here Professor Westfall shows us all that we completely miss the opportunity to teach what object oriented programming is all about from the start. It's no wonder kids have trouble with the concepts in AP Computer Science. They teach an old paradigm from the beginning of the course and it carries through until students are forced to make a pardigm shift to Object Oriented programming. Kind of silly when the pardigm has been in force for over 15 years. This is what I had to do as I shifted from C to C++/Java. Only I had a lot more time to do it than 1 year. Infact, much of my early work in C++/Java had very little to do with the new object oriented paradigm. I was just doing structured programming in these new object oriented languages. I had to come to terms with the new paradigm because I was firmly rooted in the "Structured" programming paradigm. But we seem to make the new generation of budding computer scientists become rooted in the old paradigm almost as if it is a rite of passage.

The following code I did from memory it is essentially the same in Dr. Westfall's article and he references the book "The Java Programming Language" as his source:

package apcompsci;
Class HelloWorld {
  static public void main (String[]args)
  {
    System.out.println("Hello World");
  }
}

Simple enough program but as Prof. Westfall points out this is just C style structured programming there is nothing object oriented about it.

Now an object oriented version. I take some liberties to be brief, like including a 'main' method in the class for testing purposes. Prof. Westfall created 2 classes to prove his point. One to implement the class(object) and another to use it. I also improve on the object oriented design from Dr. Westfall's article (he uses a static method which undermines the object orientedness of his original example a bit at least in my opinion).

package apcompsci;
Class HelloWorld {
  String greeting;
  HelloWorld(String s) {
    this.greeting = s;
  }

  // The @Override is to overide an already existing method in the Object class
  // this flags the method for Javadoc and netbeans purposes.
  @Override  
  public String toString() {
    return this.greeting;
  }
  static public void main(String [] args) {
    HelloWorld hello = new HelloWorld("Hello World");

    System.out.println(hello);
  }
}

The output of the above two programs is the same. You wouldn't be able to tell just from the output which one is the object oriented version. But Object Oriented programming isn't concerned with output it is concerned with better program organization to obtain the output. For simple programs the organizational improvement is certainly less impressive. But as you create more complex programs the improvements should be self evident. For what it's worth I believe my programs done in Java are much easier to understand and maintain than any of my previous work done in structured programming languages.

Basic Tenets of Object Oriented Programming: Inheritance, Polymorphism, Encapsulation

Inheritance

I won't go into a long explaination about inheritance except for the fact that the object created above implicitly (meaning the compiler does it for me) inherits from the Java 'Object' Class. So if you have been writing programs in Java you have automatically been using the inheritance features of Object Oriented Programming. As a foreshadowing yet to come (in another blog post) inheritance allows you to take somebody's Object implementation and add to it ('extend' is the Java term) for your own nefarious purposes. But without having to change the code of the original object. This is a great strength of Object Oriented programming and is very helpful on large multi-programmer projects where you need to borrow functionality that has already been tested by another programmer.

Polymorphism

The name is scarier than the actual concept. In fact you may have been making use of it without knowing what it's called. I won't give you a proper definition (I don't feel like adding a reference). But it means that you can reuse method names for different parameters and the compiler will match up the calls based on what the Java 'Class' of the parameter is. The typical example would be an object that performs calculations. You may want to perform the calculation allowing an integer parameter or a double parameter. In this case you define a calc(int i) method and a calc(double d) method. When you go to use your methods for example obj.calc(2) or obj.calc(2.3) the compiler figures out that 2 is an int so use the calc method with an int parameter and that 2.3 is a double so use the method with the double parameter. In the old days you would have to have unique names for each method call which is tedious and confusing since the probably do almost identical calculations.

Encapsulation

Encapsulation includes data hiding. The user of an object should not have to be burdened with the underlying implementation of fields and methods. The maker of an object should publish a set of documentation that explains how to create an object and what messages must be passed to the object to cause the desired functionality to occur.

In the case of the code above we can hide the call to System.out.println. The user of an object should not have to know exactly how to draw it or print it onto the screen. The object should take care of that. Just as we hide data inside the object definition, object oriented programming also says to hide the method (procedures in old Computer Science speak) implementations inside the object as well. Then by sending a message to the object we get the functionality we expect. It's all tied up in a neat little package defined in our Class implementation. So a stricter implementation would be:

package apcompsci;

/**
 *
 * @author nasty
 */
public class HelloWorld {
  String greeting;
  HelloWorld(String s) {
    this.greeting = s;
  }

  public void print() {
    System.out.println(this);
  }

  // The @Override is to overide an already existing method in the Object class
  // this flags the method for Javadoc and netbeans purposes.
  @Override
  public String toString() {
    return this.greeting;
  }

  static public void main(String [] args) {
    HelloWorld hello = new HelloWorld("Hello World");

    hello.print(); // sends a 'print' message to the object
  }
}

This may seem trivial but consider a more complicated project with an object with complex data fields. A 'print' method would be very handy for a programmer to have. Programmers could get meaningful output without having to rely on 'insider' knowledge of the object definition. This is a main feature of encapsulation to hide details inside the object and give programmers a well documented series of method calls in which to do useful things with the object.

Now let's take it a step further. Once I have this HelloWorld object class implemented I am no longer limited to just creating one HelloWorld object. I can create multiple objects each with a different text. Then I can print each one out by sending a 'print' message to each object. In Java we send messages by the following syntax:

<object_name>.<method_name>(<parameters_if_any)

Yes this is just what used to be known as a procedure call but in object oriented programming there is more going on than meets the eye. Under the covers the code is keeping track of what to call and where the definition for that code exists (remember there is something called inheritance that goes on beneath the covers so the code may not even be in your object definition). So now a multi-object version of HelloWorld class would look like:

package apcompsci;

/**
 *
 * @author nasty
 */
public class HelloWorld {
  String greeting;
  HelloWorld(String s) {
    this.greeting = s;
  }

  public void print() {
    System.out.println(this);

  }
  // The @Override is to overide an already existing method in the Object class
  // this flags the method for Javadoc and netbeans purposes.
  @Override
  public String toString() {
    return this.greeting;
  }

  static public void main(String [] args) {
    HelloWorld hello = new HelloWorld("Hello World");
    HelloWorld hi = new HelloWorld("Hi World");
    HelloWorld hello_german = new HelloWorld("Guten Tag Welt!");

    hello.print(); // sends a 'print' message to the object
    hi.print();
    hello_german.print();
  }
}

The output looks like this when run under the Netbeans IDE (IDE stands for Integrated Development Environment ie. the program you use to construct Java programs):

run:
Hello World
Hi World
Guten Tag Welt!
BUILD SUCCESSFUL (total time: 2 seconds)

Improved (or more complicated depending on your perspective) a bit further

package apcompsci;

/**
 *
 * @author nasty
 */
public class HelloWorld {
  String greeting;
  HelloWorld(String s) {
    this.greeting = s;
  }

  public void print() {
    System.out.println(this);

  }
  // The @Override is to overide an already existing method in the Object class
  // this flags the method for Javadoc and netbeans purposes.
  @Override
  public String toString() {
    return this.greeting;
  }

  static public void main(String [] args) {
    HelloWorld hello = new HelloWorld("Hello World");
    HelloWorld hi = new HelloWorld("Hi World");
    HelloWorld hello_german = new HelloWorld("Guten Tag Welt!");

    hello.print(); // sends a 'print' message to the object
    hi.print();
    hello_german.print();

    // Let's use an array of objects and a loop and see what it looks like
    HelloWorld[] hellos = {null, null, null}; // This creates an array of null
    // I need to fill the array with some actual objects
    hellos[0] = hello;
    hellos[1] = hi;
    hellos[2] = hello_german;

    // Now print them in reverse order from the first time
    for (int i = 2; i >= 0; i--) {
        hellos[i].print();
    }
  }
}

The Output:

run:
Hello World
Hi World
Guten Tag Welt!
Guten Tag Welt!
Hi World
Hello World
BUILD SUCCESSFUL (total time: 2 seconds)

Take a good look at the array code above and try to understand it. This could become the start of a section of code to take greetings from a file and turn them into HelloWorld objects. You could then create a program that reads in the file, creates an object for each line of text in the file and then gives you a random greeting from the text you read in. While you may be wondering what is the possible use of something like the code above. Let's just say instead of text these were objects drawn on the screen. This small piece of code could be the start of a drawing program. As you create more and more objects you don't want to be writing out individual variable names for each one do you? No you want to store them in an an array or list and use loops to go through each of the objects to do useful things. Make the computer do all the work so you don't have to.

References

1. Dikstra, Edgar. “Go To Statement Considered Harmful.” Communications of the ACM 11.3 (1968): n. pag. Print.
2. Westfall, Ralph. “Hello, World Considered Harmful.” Communications of the ACM 44.10 (2001): 10–11. Print.
3. Arnold, K. and Gosling, J. "The Java Programming Language" 2nd edition Reading, MA: Addison-Wesley 1997 Print.
4. Wirth, Niklaus. "Algorithms + Data Structures=programs" Englewood Cliffs, NJ: Prentice-Hall, 1976. Print.

Author: Nasty Old Dog

AP Computer Science: It's Not Just Programming

Computer Science is more useful than you know

My AP Computer Science musings in this blog are based around my son's experience at learning programming concepts as taught in his AP Computer Science class. I did not have the priviledge of AP Comp Sci when I was in high school. But being an IBM brat (my dad worked for IBM research) I was lucky to have an early exposure to computers as a kid. Initially it was playing blackjack on the APL/360 system as I waited for my dad to tweek an experiment and then take me to the cafeteria at Watson Research famous for it's handmade chocolate shakes and it's display of Leonardo Da Vinci invention models. So before high school even started I had a basic familiarity with computers and programming.

Our modern era with window based operating systems and downloadable applications my kids have exposure to computers I only dreamed of at their age. But it seems that their view of the computer is much the same as the microwave oven, you turn it on and it does stuff. The idea of programming the device themselves is not something they are concerned with. In my era the only way for the computer to do something useful was to program it yourself. Today you can download dozens of free programs that can do almost anything you could want, which further reinforces their attitude.

I don't believe I can really convince them that it is a necessary skill (though it is), but I can force them to take the course. You may think I am forcing them to follow in my footsteps. But there are necessary skills they receive from learning how to program. There are management skills embedded in the practice of computer programming and it helps enhance their understanding of mathematics. Computer Sciences provides the following management training skills:

• The simple process of writing down a set of instructions clearly and concisely
• The ability to break a problem down into smaller more manageable tasks
• Completion skills

The last skill is something we all struggle with constantly. It is an imprecise skill. But a Computer Science student learns intuitively when a project is finished (it's not when you finish typing the first draft). When a deadline looms they learn the skill of focusing the project on its most important elements to maximize their grade (given the fact that it's 2am and they need to get something working and get to sleep). This is the stuff that people get an MBA for and yet it's available in it's own experimental laboratory called the computer.

How you tackle a computer program would be the same way you tackle creating an assembly line to make a product. There are certain inputs and outputs. Certain raw materials that must be brought into the process. The finished product must be packaged and shipped. All of these things go on in a computer with bits and bytes for the raw materials and a print out for the finished product. These skills translate directly into business. It is because of this that large corporations use computers up and down the company ladder. Computers to control manufacturing, sales, shipping, and accounting. The 21st century manager must have a knowledge of what can be automated because it goes hand in hand with basic problem solving.

Author: Nasty Old Dog

AP Computer Science the Problem with Java

The AP Computer Science class relies on Java as the underlying computer language. There are some benefits to this choice the main one being that Java avaialable on almost any type of computer. Java is also an object oriented language. Object Oriented programming being current state of the art in Computer Science. Many Software Engineering principles now in practice are easily implemented in Java. The Java language takes advantage of the 50+ years of software experience providing support for Strings, threading, and provides a packaging system allowing programmers easy access to class libraries that provide incredible functionality.

So what's the problem?

The problem is that Java does such a good job of abstracting (ie. hiding) away the details of programming it virtually insulates the beginning programmer from learning programming fundementals. Strings are the perfect example. When a beginning programmer works with strings in Java they have no idea how these strings are implemented.

• How are they stored?
• How does the String class track the length?

Java's ancestor the C programming language these are issues the student must grapple with ad-nauseum.

In C, string processing routines are usually the next step after the quintessential "Hello World" program. Not because C doesn't provide string processing routines, it does. But because the manipulation of strings provide an introduction into "looping over memory locations to calculate an answer" (this is what we loosely call "looping" but all that other stuff happens in the loop as well). The understanding of loops in the simple context of characters stored in arrays presents the student with some important concepts. First that these characters are stored in a contiguous block of memory. That the computer has no ability to process these characters enmass. They must be accessed individually. They learn about what I call "boundry conditions". For example, when implementing a string the student must come up with some way to recognize the end of the string (the boundry). They find out that logical equals only works with simple types, you can't just say:

if (char_array1 == char_array2)

That to show equivalence you must:

• loop through the array
• check the characters in each string
• individually compare each character with logical equals.

That to put two strings together (a procedure called concatenation) you need to:

• loop through both strings
• move the characters to a new block of memory set aside for the new string
• the new string will now contain all the characters from both strings combined in one place

In computer science these looping patterns are repeated in many other situations but with more complex data. For the begining student, however, the complex data becomes the focus instead of the important looping patterns. Indeed students find they don't even know where to start because they don't have a simple example to fall back on. In Computer Science the very key to abstraction is having a solid foundation in basic principles. Abstraction occurs because you recognize a more basic pattern can now be applied to a complex situation.

Rather than advocating a different language than Java as the language of choice for AP Comp Sci (after all I love the language). I decided to put together a String class that implements Strings with char arrays. The array mechanism in Java is a little closer to how C represents arrays. The issues in implementation are about the same and the looping patterns are all preserved. The story continues within the comments inside the code below.

/*
 * APString class
 * The idea is to create a string class that uses arrays to hold the characters    
 * This methodology is closer to how the actual hardware is organized.
 * The String class in Java has built in support. In fact any double quoted 
 * String is itself a String class object. "a string".toString(); is valid
 * Java code and all of the methods of the String class may be used above
 * in place of toString().
 * 
 * Java hides much of this organization because it is object oriented and    
 * there is a long history of String operations in computer science. So the    
 * designers (rightly so) added String handling capabilities in the language 
 * itself. However for people trying to learn about computers for the first    
 * time this shielding (known in computer science terms as abstracting) of the
 * lower level organization is a disservice. While Strings are well known the 
 * patterns of their processing are repeated enough for other things that a 
 * thorough understanding of the low level processing of Strings will only help    
 * the new Programmer/Computer Scientist.
 * 
 * Indeed Donald Knuth in his classic treatise "The Art of Computer Programming"
 * goes so far as to invent a ficticious computer with a ficticious 
 * assembly language to bring to light the issues of computer architecture and
 * their effect on the design of computer programs.
 */
package apcompsci;

/**
 *    
 * @author nasty
 */    
public class APString {    
    // It's not necessary to limit a char array like this. Java will
    // dynamically create space as needed but in some computer languages    
    // they must be allocated out ahead of time. So as a place holder we
    // define our initial array as 100 chars.    
    char chArray[] = new char [100];
    int len;    

    APString(char chArray[])
    {
        // Let's copy the char array given into the one we defined above as
        // part of the class    
        int i = 0;
        for(i = 0; i < chArray.length; i++)
          this.chArray[i] = chArray[i];
        this.len = i;    
        this.chArray[i]='\0';    
        // The above '\0' is the ASCII null character. By setting the very
        // last character to this value it acts as a flag to let us know
        // we are at the end of our string. The length() method uses this to
        // calculate the length of the string
        // I also implemented a len field to store this in. It is left to 
        // the reader to reimplement this class with a length field and get
        // get rid of the null termination. This would save a lot of looping
        // over the string to get the string length    
    }

// All classes defined in Java have a base toString but because we have
// defined some fields as part of our class we need to convert those to 
// Strings so we can print them out and we override the base toString features
//
// It's unfortunate but we must rely on the built-in String class because    
// they are used by all the print procedures
@Override
    public String toString()
    {
        String s = "";

        for (int i = 0; i < this.len; i++)
            s = s + this.chArray[i];
        return s;
    }

    public int length()
    {
        int i = 0;    
        for (i = 0; this.chArray[i] != '\0'; i++)
        {
            // Do nothing just let i keep count and keep looping until we hit
            // the null character which will break the test above
        }        return i;    
    }

    // reverse - create a new APString that reverses all the characters in    
    // the current class. Except for the null string we don't want that to 
    // be our first character. WHY?
    public APString reverse()
    {
        char tmp[] = new char[this.length() + 1];
        int j = 0;
        for (int i = this.length() - 1; i >= 0; i-- , j++)
        {
            tmp[j] = this.chArray[i];
        }
        tmp[j] = '\0';
        return new APString(tmp);
    }

    /**
     * @param args the command line arguments    
     */
    public static void main(String[] args) {
        // Since we are trying to avoid the use of the built-in Java Strings
        // we are forced to define strings by initializing a char array
        // I think you can see why it's so nice to have Strings built into
        // Java. Imagine having to define every string like this:
        char[] a = {'T','h','i','s',' ','i','s',' ','a',' ','t','e','s','t','\0'};
        APString ap = new APString(a);
        // Using the String double quotes built in the followin is an equivalent
        // statement:
        // APString ap = new APString("This is a test".toCharArray());
        System.out.println(ap.toString()+ "   length = " + ap.length());
        System.out.println(ap.reverse().toString());
    }
}

Some exercises

1. Left for the reader to accomplish is a compareTo (or equals) method. That will take an APString parameter and compare it to the current value stored within the object.
2. Create a constructor that takes a Java String class parameter and constructs an APString instance. This will allow you to define APStrings with "This is a string" syntax.
3. Make a findreplace method that accepts a search string and a replacement string. Search the objects string for the search string and replace it with the replacement string parameter.

References

Much of the above I garnered from years of reading the following references:

1. Knuth, Donald E. The Art of Computer Programming. 3rd ed. Vol. 1-3. N.p.: Addison-Wesley Pub., 1999. Print.
2. Kernighan, Brian W., and P. J. Plauger. Software Tools. Reading, MA: Addison-Wesley Pub., 1976. Print.
3. Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. Englewood Cliffs, NJ: Prentice Hall, 1988. Print.

Author: Nasty Old Dog