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