• Preface
• CS1 and CS2 Syllabus Design and Explanation
• Method or Function Call and Return
• Complete Applications
• Tracing Program Codes
• Misconceptions
• Memory
• Variables and Objects
• References to Objects versus Objects
• Arrays
• The array object
• Examples
• Graduated Series of Examples 1
• Java and Unix Command Line Introductory Lab Exercise
• Command Line Develoment
• Timing
• Understanding Syntax
• Frontiers
• Advanced Misconceptions

Method or Function Call and Return

What is a function or method call and a return?

For the purposes of this topic, functions and methods are the same thing.  In Java, in fact, this thing is always called, technically a method.  In some older programming languages, they are also called procedures, and in others, subroutines.

The original purpose for methods, which is still very relevant, is to enable executable code intended to be run at often many different places and times to be written only once, and not copied or rewritten at each place in the program where is is supposed to be run.

  Naturally, this purpose requires you to do two different things:  First, you must actually write the code to be written only once in a way that it can be run from many other places.  That is called defining the method.  Defining the method requires that you write both the method's name and its body: The body is the single copy of code written once.  Second, at each place in the program where the code written in the method is supposed to be run, the name of the method must be written.  This is called writing the method call.  When the method call you wrote is encountered when computer actually runs your program, the code written in the body, having been written a long time ago to define the method, is actually run by the computer.  Encountering the method call and getting the code written in the method's body to run is called calling the method; one occurrence of calling a method is called a method call.

 Inside a method body, the return operation can be coded.  In Java, sometimes, the return operation need not be written explicitly; in that case, the return operation is still there and it supplied automatically after the last line of code in the body.  When the code of the body is run, the return operation makes the computer go back to where it left off when the method was called.  That action of going back is called a method return.  Every method call is eventually followed by a corresponding method return, except if an exception occurs or if the program execution or computer fails first after the method.

The second purpose for methods, which is an innovation of object oriented programming, is to tightly attach data processing behavior to chunks of data of a particular kind, called objects.  (In Java, there is another kind of method whose call is not attached to an object but instead is associated with a class.  It is termed a static or class method.)  The chunk of data, that is, the object to which the method is attached is called an instance.  The kind of method who calls are always attached to instances is instance method.  

In Java, a method call is always written as the name of the method followed by a matching pair of parentheses.   If the method has parameters, the parameter values are supplied by expressions within those parentheses, separated by commas if there are more than one parameters. 

Static and Dynamic Structure

When methods call one another, two kinds of structure emerge: Static and dynamic.  One static structure is determined simply what names of methods ¹ appear.  Another is the dynamic structure.  The dynamic structure comprised of things called activations. An activation is both a record of data in the computer memory and the period of  time between when a method is called and when that same call returns.  It's like the life of a cat or other mortal creature: The life surely involves the cat's body when it is alive and the period of time between its birth and its death. 

 The distinction between an activation of a method and the method itself must be clearly understood. That distinction is just like the distinction between the idea of what a cat is distinct from the life of one particular cat that it's owner knows and loves.

Understanding Activations: The Dynamic Structure

We present two kinds of diagrams to visualize the dynamic structure.  One portrays the traditional stack of activation records.  This appears in most books on programming.  Indeed, this stack exists explicitly in computer memory during runtime.  Unfortunately, it only portrays information about a single moment of time.  As soon as the current activation either calls another or it returns, the contents of the activation record stack change!  The dynamic behavior must be explained separately, or by a sequence of different images of the stack, taken at different times.

  A less popular kind of diagram lets us visualize all of the activations that had been created and had returned during the entire run of the program.  A form of this diagram is used in algorithm books such as Introduction to Algorithms by Corman, Leiserson, Rivest and Stein. It is there used to account for the computer time consumed by each activation.

We will name the diagram of all the activations, where each activation may be annotated with  the method name, that activation's parameters and its return value an activation history tree.  It the activation history tree, time proceeds from left to right.  We then observe that the temporal sequence of calls and returns is simply a combined pre and post left-to-right order of the tree edges or branches.  Finally, we might express an application of mathematical induction to an correctness argument by omitting all the activations below a particular one.  We would explain that we assume by mathematical induction each of the omitted activations correctly performs the computation documented for the omitted activations.  Of course, it must be verified that the parameters for each omitted activation are less than the positive integer (say² ) we are doing induction on; and that the base cases have been justified.

Here is an example for a simple recursive method that prints a sequence strings stored using a linked list first forwards and subsequently backwards.

And here is an example for the famous Towers of Hanoi recursive solution:

Exercise: Draw all the activations that would be in the spaces marked "not shown" to complete the activation history tree for the solution to the 3-disk Towers of Hanoii puzzle.

And finally, the example of MergeSort:

Programming Problem Scheme:

Take any problem whose solution is programmed with methods calling one another, including recursive solutions.  Implement the solution and make each method print an informative message as soon as it is called.  Also, add a depth parameter to each method and method call.  (Give each method (except main) a parameter named depth, say at the beginning.  Then change every method call to have the form methodname(depth + 1, ...).)  Finally, make each informative method be printed indented by depth spaces.  The computer will then draw the activation history tree!

Stack Diagrams

These are useful for teaching about the activation stack, and especially relating the stack, as a famous abstract data type, to the execution of programs with methods calling one another.  This is absolutely necessary for one to use a debugger effectively.

How the stacks³  of activation records (plus static variables) bases the accessible dynamic objects

 

1. The same named method belonging different classes or with a different argument signature is considered to be differently named method. Our simple kind of structure may need to be replaced by a more complicated one also when virtual methods are considered. Note that in Java, all non-static methods are virtual. ^{^}
2. Induction can in the same manner be justified on any appropriate partially ordered set when such additional mathematical sophistication contributes to a easier proof of more complex assertions.^{^}
3. There is a separate stack for each thread.^{^}