Recursion

In the beginning there was the SUBROUTINE.

In the early days of programming there were no large standard libraries available. There were a small set of routines that gave the programmer access to operating system facilities like printers and screen output. In some languages these were built right into the language, much the way Java has some built in constructs for the String class.

In assembly language programming, a language to code directly in the codes the CPU (Central Processing Unit) understands, there is a 'JSR' statement. 'JSR' is a mneumonic that stands for Jump SubRoutine. In an assembler language program this means to jump to a 'label' placed in your code then, return when the 'RET' statement is hit. Return to where? To the statement right after the 'JSR'. It's much like when your playing a video game and your mom asks you to do the dishes or take out the garbage. You, as your very own CPU, pause the video game, go and accomplish the chore, then return right back at the video game picking up exactly where you left off. The problem for the assmebly language programmer is that these statements do not allow parameters. The programmer must take care of all of that themselves in the assembly language code

FORTRAN was one of the very first computer languages developed. It's short for Formula Translation. It's big claim to fame was to provide the user with variables and arithmetic operators built into the language. This became a main stay of Engineers and Scientists who wanted to solve difficult mathmatical problems. Fortran also provided a feature called SUBROUTINEs. It had a SUBROUTINE statement and better than it's assembly language counterpart it allowed you to define parameters and use them in your programs. In fact there is not much difference between the look of a FORTRAN SUBROUTINE and a Java method. Java is a little fancier there are 'public' and 'private' methods. There are 'static' methods. In the early days of FORTRAN you didn't have to worry about this every SUBROUTINE was 'static' SUBROUTINEs never return a value because FORTRAN had FUNCTION statements for that.

FORTRAN also had a CALL statement so you could execute your SUBROUTINE. This is why you may hear people talk about a 'Method Call' or an instructor may say "Don't for get to call your method". Computer Science has a very informal language when we talk about various topics, but we try to use different terminology when we can to better describe what we are doing. The example here is that I may tell you to 'Run' your method and you may understand what I mean. But more formally you 'Run' a program and the program 'Calls' your method.

A SUBROUTINE can call other SUBROUTINEs

The whole point of this stroll down memory lane is that once the syntax of the subroutine became establised, there was a natural inclination to allow a SUBROUTINE to call itself. We already had recursive definitions as part of mathematics. So now that we have computers that animate our mathematics for us, the push for recursive SUBROUTINEs was on.

It may seem that it should be self-evident that a SUBROUTINE can call itself but in the early design of computer languages it turns out you must do some special things under the covers to get this to happen. So newer languages that followed after FORTRAN made sure they had these capabilities. I won't bore you with a cronology of how recursion came into being. There were languages in existance at the time of FORTRAN that already had it. But suffice it to say that when Personal Computers came about and the C language (a predecessor to Java) dominated the programming of that platform, C had built in recursion. Lucky for you! because it's a pain to simulate recursion in a language that doesn't have it. Java as an ancestor of C also has recursion built in.

METHODS ARE JAVA SUBROUTINES

As languages change so does the nomenclature. SUBROUTINEs are now methods. Methods don't even have a METHOD statement like SUBROUTINES do. This is because after people became very familiar with FORTRAN they realized that a SUBROUTINE definition can be recognized by:

• it's name
• the parenthesis that follow
• and the parameter definitions inside the parenthesis

So by the time Java comes around we expect you as a newbie just to pick up on this on your own. If you are an older programmer you know you got sick of writing SUBROUTINE for each and every SUBROUTINE definition. That's a large amount of typing saved (well kind of there are things like public and void but they are much shorter words. We even dropped a formal statement for calling the SUBROUTINE. Now you are just supposed to know that any name followed by parenthesis with comma separated parameters is a Method call. Methods have all the stuff of a subroutine but now are grouped into objects (ie. class definitions). They can be inherited and they can be overridden. These are certainly things that don't happen with SUBROUTINES. The name change is fitting since the old fashioned SUNROUTINES have more in common with "static" methods than with methods in general.

METHODS can call themselves

Recursion being well established in computer science methods can call themselves, it's built in to the language. The danger of course is that the programmer must make sure they have accounted for any and all 'base' cases, otherwise the code will run forever! Well, not forever you eventually run out of memory.

Recursive definitions

The first example is always factorial. Sorry about that. But it has a simply stated recursive definition so it is popular. Students usually focus on factorial being so trivial to implement that they feel recursion is senseless since you could do it easily with a loop. But like so many things in computer science the trivial case is foreshadowing of more complicated stuff yet to come.

Factorial

factorial (n) = 1 (for n = 1)

                   = factorial(n-1) * n (for n > 1)

Fibonacci numbers

Fib(n) = 0 (for n = 0)

           = 1 (for n = 1)

           = Fib(n-1) + Fib(n-2) (for n > 1)

This is a better example for recursion. It does not have a trivial loop alternative. That's not to say you can't create a loop that can do it. Every recursive implementation has a looping counterpart. It's just that it's not trivial like factorial is. The double calls to Fib above do us in for coming up with an easy looping code design.

This type of recursion is termed tree recursion by Abelson and Sussman in their classic work "Structure and Interpretation of Computer Programs"(known in computer science circles as just SICP). That's because if you were to draw out all the recursive calls at each step, you would form an inverted tree with the first call leading to 2 calls and those two calls lead to two calls and so on.

Greatest Common Divisors

Given 2 integers this is the greatest integer that divides both of them evenly. It is very helpful when you are trying to reduce fractions to lowest terms.

Gcd(a,b) = a (for b = 0)

             = Gcd (b, remainder(a,b)) (for b > 0)

If you think the above definition is some modern mathematic torture dreamed up to make your life a living hell. Abelson and Sussman point out that the above definition appears in Euclid's Elements Book 7 circa 300 BC. So the reality is that mathematicians have been developing torturous problems for their students from time immemorial.

Your Job

I leave it up to the student to implement these functions. If your interested there are more recursive functions defined in the SICP which is available online. There are also Scheme Programming Language examples of their implementation. That may assist you with the Java implementation or it may confuse you more.

Princeton University has an excellent collection of recursive functions at their introduction to computer science web site. Their site includes a large number of implementation examples. I would suggest you try to implement the examples above and then visit their site if you have any problems. http://introcs.cs.princeton.edu/java/23recursion/ The link to Princeton's course is here: http://introcs.cs.princeton.edu/java/home/ This includes a much broader perspective also going over some computer architecture which I believe is incredibly helpful when you are trying to make sense of computer science in general.

What No Code?

Of course there is code. It wouldn't be a comp sci article without code. Using our previously defined APString class I will implement a reverse method that uses recursion to reverse the elements of our string. Now, because we have no built in operators for the APString class (such as string concatenation), we can't do a simple recursive routine that's possible with the Java String class. Actually that's a good idea let's first look at using recursion with the Java String class.

A simple recursive methodology for Java Strings would be the following:

1. take the first character of the String and store it as a string
2. reverse the rest of the string after the first character is removed
3. concatenate the new reversed remainder with the first character added to the end.

Step 2 has the recursion in it if I name the method 'revStr' the pseudo code will look like:

String firstch;
String restStr;

// ignore the base case for now
firstch = str.subString(1,2);
restStr = str.subString(2);
return revStr(restStr) + firstch;  // concatenate the first character onto the end of the string

Take some time to think of what the base case is for the code fragment above. I went ahead and implemented the whole code and placed it at the end of the article but given what I have done above you should be able to code the whole thing yourself. Go ahead and see if you can reverse a Java string recursively in your own Java IDE. I would create a separate class for this assignment and give it it's own main method. Then once you have it working compare it to the code at the end of the article.

APString reverse done recursively

This was not such an obvious recursion because there are no built in facilities for APString like the concatenation operator that the Java String has. We have not even implemented a concatenation method or a substring method. So you can see the time savings that Java provides and the difficulty we have trying to duplicate the same functionality in a class of our own. I will add those in a future article and try to implement reverse as we did for the Java String class.

Since we don't have the benefit of the methods described above I will take advantage of a Java method for arrays.

Arrays.copyOfRange(<array variable name>, start index, end index).

This is provided by the Java class library. It's kind of cheating because I don't have to make my own copy routine, which would probably loop through all the elements of the array. Since we have to loop why bother reversing the string recursively other than to show how you can think of problems recursively? Well, that's the point really. There are times when a looping construct is the best mechanism but there are times when recursion will help to simplify your code. Most of the time you will have to try both and see which one provides you with an elegant solution.

Design of the recursive algorithm

The APString class uses char arrays to implement it's String functionality. We will need a temporary char array to hold the reversed elements and to be our working storage as we change the order of the characters. We could do this in the char array we use for the object itself but then this would actually change our object rather than providing a new object with the desired results. This also means we need to return an object of APString as the final result. This creates a problem for recursion because I want to recurse on the char array and then return an APString when all is done.

• Design Requirements
  1. return an object of APString
  2. create a recursive routine to recurse on char array
  3. use a temporary char array to be the working storage
  4. Don't let any of our methods change the underlying values of our original APString object

This means we will need 2 methods instead of one. One method to setup our working storage and return an APString value and another method to do the recursion on our working storage.

Recursive method and setup method

// reverse_array recursive helper procedure for reverser
// 
private void reverse_array(int startIdx, int endIdx, char ch[]) 
{   
    char tmpch;
    // base case 1: odd length we have reached the middle element
    if (startIdx == endIdx) 
        return;
    // base case 2: even length array the indexes are side by side
    if ((endIdx-startIdx) == 1) 
    {
        tmpch = ch[startIdx];
        ch[startIdx] = ch[endIdx];
        ch[endIdx] = tmpch;
        return;
    }
    // recursive case swap current indexes then recurse on the rest
    tmpch = ch[startIdx];
    ch[startIdx] = ch[endIdx];
    ch[endIdx] = tmpch;
    reverse_array(startIdx+1,endIdx-1,ch);        
}

 // The intial call to set up the recursive routine above with working storage array
public APString revStr() {
    char[] tmparray = Arrays.copyOfRange(chArray, 0, this.length());
    reverse_array(0,this.length()-1,tmparray);
    return new APString(tmparray);
}

The main method used to test the above code

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 following is an equivalent
    // statement:
    APString ap1 = new APString("This is a test".toCharArray());

    System.out.println(ap.toString()+ "   length = " + ap.length());
    System.out.println(ap1.toString()+ "   length = " + ap1.length());
    System.out.println(ap.reverse().toString());
    System.out.println(ap.revStr().toString());
    System.out.println("No change to original: " + ap.toString());
}

And the output from testing:

run:
This is a test   length = 14
This is a test   length = 14
Looping reverse: tset a si sihT
Recursive reverese: tset a si sihT
No change to original: This is a test
BUILD SUCCESSFUL (total time: 0 seconds)

The whole APString code with the recursive procedures built in

/*
 * 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;

import java.util.Arrays;

/**
 *
 * @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);
    }

    // reverse_array recursive helper procedure for reverser
    // 
    private void reverse_array(int startIdx, int endIdx, char ch[]) 
    {   
        char tmpch;
        // base case 1: odd length we have reached the middle element
        if (startIdx == endIdx) 
            return;
        // base case 2: even length array the indexes are side by side
        if ((endIdx-startIdx) == 1) 
        {
            tmpch = ch[startIdx];
            ch[startIdx] = ch[endIdx];
            ch[endIdx] = tmpch;
            return;
        }
        // recursive case swap current indexes then recurse on the rest
        tmpch = ch[startIdx];
        ch[startIdx] = ch[endIdx];
        ch[endIdx] = tmpch;
        reverse_array(startIdx+1,endIdx-1,ch);        
    }

     // The intial call to set up the recursive routine above with working storage array
    public APString revStr() {
        char[] tmparray = Arrays.copyOfRange(chArray, 0, this.length());
        reverse_array(0,this.length()-1,tmparray);
        return new APString(tmparray);
    }

    /**
     * @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 following is an equivalent
        // statement:
        APString ap1 = new APString("This is a test".toCharArray());

        System.out.println(ap.toString()+ "   length = " + ap.length());
        System.out.println(ap1.toString()+ "   length = " + ap1.length());
        System.out.println("Looping reverse: " + ap.reverse().toString());
        System.out.println("Recursive reverese: " + ap.revStr().toString());
        System.out.println("No change to original: " + ap.toString());
    }
}

Recursive reverse on the Java String class

package apcompsci;

/**
 *
 * @author Nasty Old Dog
 */
public class NODString {
    public String revStr(String s)
    {
        String firstch;
        String restStr;

        // base case s length is 1 just return s
        if (s.length() == 1)
            return s;
        // recursive case
        firstch = s.substring(0, 1);  // get the first character
        restStr = s.substring(1);     // get the rest of the string

        // reverse the string by moving the first char to the end and the
        // reverse of the rest of the string on the front.
        return revStr(restStr) + firstch;   
    }

    public static void main(String[]args)
    {
        String teststr = "reverse this";
        NODString nod = new NODString();
        System.out.println("The reverse of "+teststr+" is "+nod.revStr(teststr));
    }

}

The output from the above program is:

run:
The reverse of reverse this is siht esrever
BUILD SUCCESSFUL (total time: 1 second)

References

1. Abelson, Harold, Gerald Jay. Sussman, and Julie Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT, 1985. Print.
2. "Welcome to the SICP Web Site." Welcome to the SICP Web Site. N.p., n.d. Web. 01 Jan. 2013. http://mitpress.mit.edu/sicp/.
3. Sedgewick, Robert, and Kevin Wayne. "Introduction to Programming in Java." Introduction to Programming in Java. Addison-Wesley, n.d. Web. 01 Jan. 2013. http://introcs.cs.princeton.edu/java/home/.

Author: Nasty Old Dog

How to Approach AP Computer Science

How to Approach AP Computer Science

After seeing the mess of papers my son considers organization and listening to the excuses as to why this course is so difficult. I thought I would provide a little guide on how to get on top of this course. It's not really a difficult course. But it requires that you don't sit on your hands and hope everything becomes clear just by staring at it. This is like my obsessive compulsive behavior of constantly opening the refrigerator door in the hopes that food will somehow magically appear (even though I'm home alone and no one has gone to the store). Now I realize that an AP Computer Science Student is young. They have been raised like veals by their parents and now they must come to grips with actually creating something instead of just using something. So first and foremost you must embrace the challenge and rise to the occasion. If you put a little effort up front it will make this course easy for you.

Start your assignment as early as possible

I know this may come as a surprise but your teacher actually sleeps. They are not creatures of the night looking for their next blood meal. So by starting your assigned project early you have a chance to email them with any questions that may come up as you try to do your project like:

Is it really due tomorrow? It seems awfully long!

The smart student who sent the email at 8pm found out at 9pm it's due 2 days from now. The dumb student who waited until 10pm and then stayed up until 3am trying to finish, then finds out (next day at school) as they go to hand in the project that it's actually due in 2 days.

Remember you are young. Your attention span is probably a minute longer than a 10 year old (sorry but that's probably what it is). You are probably a little arrogant so you are completely poo-pooing the previous sentence, and are convinced you don't miss a thing the teacher says. To you I have some advice:

1. Make sure you have your teacher's email. Make sure you use it if you have any questions or complaints
2. Make sure you have the email, home phone, and cell phone of at least 2 people taking the class (because maybe your teacher actually has a life and is unavailable when you need him or her most)
3. If you have a class where you have no idea what the teacher is talking about make sure you talk to the teacher after class (or after school), Take notes and write down key words you don't understand so you can look them up at home. After you find or get an explanation call a friend in the class and see if that is their understanding as well
4. If you are doing a project and it seems too complex for the amount of time alotted contact the teacher and a friend and see if you are mistaken about the deadline or misguided about how to approach it.
5. Take notes in class they just have to be a quick outline of what was discussed so you can review
6. Make sure you know where the teacher's web site is located. It's a computer course they probably have all the handouts online.
7. I can't stress 1 and 2 enough so go look at them again.

Print Stuff Out

I know we are supposed to save trees but do yourself a favor and kill a few (if you have big a problem with that find recycled computer paper). Print out your assignments. Write on them, model the code on them. When you have completed the project make a printout of your code and keep it with the problem statement for you to review. The projects are set up to teach you different aspects of Computer Science they become their own review sheet.

Keep a course 3 ring binder (loose leaf notebook in my day)

Dr. Frederick Brooke in his classic work on Software Engineering talks about a large programming project at IBM back in the 1960s. Now this project hired the best of the best from within IBM and the project did one thing that kept every one on the project synchronized. They kept a set of project notebooks and in it went all the design docuemts and all the user documentation, everything.

So if it's good enough for the top people at IBM I think you should be doing it to. Keep a notebook. At a minimum: a hard copy of all your programming assignments should be in there, any notes you may have taken, and any handouts that the teacher has given you. Even though much of this is available electronically keep a hard copy around. Trust me the very fact you keep and update the notebook will mean you absorb more knowledge about the subject.

Know the language syntax

In AP Comp Sci that means: know the full Java syntax for anything you may choose to do in Java. The wikipedia website's page on Java syntax is as good as any. You should take a weekend and make sure you know how and why you use each feature of the syntax. If there is time you should get a small piece of code working showing the major control statements available in Java (if, for ,while, switch). Do not wait for the teacher to introduce this stuff to you. Do it on your own and be ready with questions when you do go over it in class.

Get the Java Library Source code

The Java development environment,known as the JDK (not JRE), on your computer usually comes with a .zip file of all the source code that implements the standard library. Be sure to unzip it and look at the various implementations for Strings, Lists, etc. It will only help you to see a good example. There is a browsable version available at http://grepcode.com/snapshot/repository.grepcode.com/java/root/jdk/openjdk/7-b147/

Get a hard copy of the textbook

I haven't found a good Java Book for a beginner. I have a number of books that I've collected over the years most are excellent references but none of them provide a decent tutorial you would want for an introductory course. My son's course uses a free online book which is available from the book's website and from Amazon as a hard cover book. I bought that. I would recommend that you get a hardcopy version of your courses text.

The hard cover book is like having a second computer dedicated to the text. Go over the teacher's reading assignments in the book don't assume you will pick it up by doing the project. Use an online version just for searching.

Get a couple of AP Comp Sci review books

These will help condense the course down and give you some more insight as to what you should be focusing on. Each book may organize the course a little differently and you may understand one better than the other. I can't really recommend one over another, but I easily found 2 review books for AP Comp Sci on Amazon.

Learn to use the cut and paste on your IDE

Programming is a repetitive process the sooner you learn to cut and paste from previous projects and similar classes the faster a programmer you will become. If you are typing everything from scratch for every project, you are wasting time. This course should get easier as you go along. Not more time consuming and difficult

Don't freak out about recursion

Just as you call methods inside other methods there is no reason a method can't call itself. It's called recursion. It exists in mathematics and it exists in programming. The trick to recursion is you must have a test built into method code that indicates when you are going to stop the recursive calls. This is just a warning of things yet to come. In the end it's not much different than a for loop. You keep looping until a test condition is reached. In recursion you keep calling yourself until a test condition is met. The Java language is set up to make this all happen. Many computer science papers exist for how to make it more efficient and less memory intensive, so it's an important topic to come to grips with.

Ok, you're freaking out anyway, I will address recursion as a topic in the future.

Finally

If you find yourself getting dinged on syntax errors on your tests, you may be better off not seeing where the errors are immediately. The IDEs (like Eclipse or Netbeans) have instant syntax checking. When you are an experienced developer this can be a time saving device. But as a new student this may be doing to much of the work for you. You aren't getting the opportunity to proofread your program before you have the computer check it. It would be nice if you could turn off the instant syntax checking. But I haven't been able to find a way to turn it off.

One way to handle would be to write your program by hand on paper first. Then type it in after you have gone over it once for syntax errors. Then as mistakes come up in the IDE you can place the corrections on your hand written program. This will give you direct feedback on where you are weak on syntax knowledge.

The other way is to drop the IDE altogether and just use an editor and then compile the program in a command line window. If you know how to do this on your computer it's a nice option that keeps you on the computer typing but forces you into proof reading your code and fixing it before you have the computer double check it. If you don't know how to do this I have it on my list of topics to address in a future blog, so more on this later.

References

Brooks, Frederick P. "The Mythical Man-month: Essays on Software Engineering." Reading, MA: Addison-Wesley Pub., 1995. Print.

Author: Nasty Old Dog

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