Difference between revisions of "Basic Programming Skills"

Revision as of 12:31, 14 March 2011

Heap, Stack and JVM

This topic touches upon stack and heap, i.e., the memory allocation, for programs in a simple way. Note: originally published in my Blogspot.

A program is run in the memory of computers. First, a compiler compiles a program into a machine representation, which is stored at some location in the memory called code segment. Other than the program itself, we need some memory allocation for methods, parameters of methods and all variables defined in a method. These objects have their memory allocated in the stack segment. A stack is a LIFO (last in first out) data structure, which always pop or push elements in it at only one open end. Additional storage of memory, the heap segment, is required for global variables and static variables (as in C), which may exist during the whole lifetime of the program.

Java_Virtual_Machine

We look further at stack and heap segment in the context of JVM (Java Virtual Machine) here.

The JVM is "virtual" in that it is an abstract computer defined by a specification. To run a Java program, you need a concrete implementation of the abstract specification. Specifically, concrete implementations of JVM exist on many platforms and come from many vendors, either software or a combination of hardware and software. On the other hand, a runtime instance of JVM hosts a single running Java application. So, the fact is a Java application runs inside a runtime instance of some concrete implementation of the abstract specification of the JVM.

Memory allocation is part of the architecture of the JVM, which might complicate things that are necessary for CS newbies. Hence, we only take a look at the basics of memory allocation in JVM.

We assume that one thread is executing a Java method (non-native method). The thread has program counter (PC) register showing the next instruction to execute and a Java stack stores the state of Java method invocations for the thread, which includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations. So whenever you see above items in a Java method, just remember that they will be put in a Java stack (which comprises stack frames, but we will not detail that).

On the other hand, as the program runs, JVM places all objects the program instantiates onto the heap segment. So, when you see a new() operator in a method, this object is created in the heap. Further, I have to say that each thread has its own stack, but the heap is shared by all of them, i.e., there is only ONE heap in a JVM instance. Recall that a Java application runs inside its "own" exclusive JVM runtime instance, so there is a separate heap for every individual running application. Different Java applications won't trample on each other's heap data. However, two different threads of the same application could trample on each other's heap data. That's why we need synchronization of multi-threaded access to objects (heap data) in Java programs.

• Arrays in Java programs

Like objects, arrays are always stored on the heap.

Contract for Programs

In software engineering, specification is a quite important step. Design (or programming) by contract is a terminology for how to design a program with possibly minimal errors using specification. The accurate specification of programs can save a lot of time and work for developers during later phases of software developing like software testing.

Intuitively, we design programs according to a virtual "contract": when method A wants to call method B, A must satisfy some conditions in order to correctly invoke B, producing intended results with some consequences. Here, we call A the caller, B the callee. The conditions attached to call B is called preconditions of B, while the consequences after calling B are postconditions of B.

In formal verification and analysis, methods typically have preconditions, postconditions and frame conditions. Frame conditions specify what can be modified after calling the method. For example, if we add an element to a list, we can have a formal specification as follows, which uses requires for preconditions, modifies for frame conditions and ensures for postconditions.

   boolean addToList(Item element, List targetList){
   //requires: element not already in targetList && element is not null
   //modifies: targetList
   //ensures: targetList' = targetList + {element}
   ...
   ...
   ...
   }

Normally, preconditions and postconditions are assertions to be made in the program. Any assertion is a predicate. A predicate is a statement that is either True or False. So, preconditions and postconditions either "hold" or "not hold" in the program. In some languages like Java, C++, we can directly use an assertion to specify some predicate must hold at certain point. Such assertions will be checked at run time, and if the compiler finds the assertion predicates are violated, the location will be pinpointed to facilitate bug finding.

We show that assertions can be deemed as the generalization of a contract. Assertions also include the specification of invariants, as we can do in a contract. An invariant, literally, means a predicate that must be True during a set of operations. In our case, we can say an invariant must hold in a method, class or program. Note that however invariants are not required to hold during all times. For instance, a class invariant may be false at certain points in that class, but as long as when we exit the class, the value of the invariant is "restored" to true, then it is OK. Typically, when we want to prove that an invariant holds in a class/method/program, it normally (not always) suffices to show that invariant hold upon the entry and exit of the class/method/program.